結果

問題 No.430 文字列検索
コンテスト
ユーザー Ogtsn99
提出日時 2025-03-28 00:51:10
言語 Go
(1.23.4)
結果
TLE  
実行時間 -
コード長 3,813 bytes
コンパイル時間 14,268 ms
コンパイル使用メモリ 240,492 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-28 00:51:41
合計ジャッジ時間 30,848 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

const (
	MOD = 1000000007
	INF = 1 << 62
)

// ==================================================
// io
// ==================================================
var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func print(x ...interface{}) {
	fmt.Fprint(wr, x...)
}
func println(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func flush() {
	e := wr.Flush()
	if e != nil {
		panic(e)
	}
}

// exit exits the program after flushing all buffers.
func exit() {
	flush()
	os.Exit(0)
}

// ni scans a single integer.
func ni() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

// ni2 scans two integers.
func ni2() (int, int) {
	return ni(), ni()
}

// ni3 scans three integers.
func ni3() (int, int, int) {
	return ni(), ni(), ni()
}

// ni4 scans four integers.
func ni4() (int, int, int, int) {
	return ni(), ni(), ni(), ni()
}

// nu scans a single uint.
func nu() uint {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return uint(i)
}

// nu2 scans two uints.
func nu2() (uint, uint) {
	return nu(), nu()
}

// nu3 scans three uints.
func nu3() (uint, uint, uint) {
	return nu(), nu(), nu()
}

// nu4 scans four uints.
func nu4() (uint, uint, uint, uint) {
	return nu(), nu(), nu(), nu()
}

// nf scans a single float64.
func nf() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

// nf2 scans two float64s.
func nf2() (float64, float64) {
	return nf(), nf()
}

// nc scans a single byte.
func nc() byte {
	sc.Scan()
	return sc.Text()[0]
}

// nc2 scans two bytes.
func nc2() (byte, byte) {
	return nc(), nc()
}

// ns scans a string.
func ns() string {
	sc.Scan()
	return sc.Text()
}

// ns2 scans two strings.
func ns2() (string, string) {
	return ns(), ns()
}

// nis scans a slice of integers.
func nis(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = ni()
	}
	return a
}

// nis2 scans two slices of integers.
func nis2(n int) ([]int, []int) {
	a := make([]int, n)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], b[i] = ni2()
	}
	return a, b
}

// nis3 scans three slices of integers.
func nis3(n int) ([]int, []int, []int) {
	a := make([]int, n)
	b := make([]int, n)
	c := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], b[i], c[i] = ni3()
	}
	return a, b, c
}

// nss scans a slice of strings.
func nss(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = ns()
	}
	return a
}

// nus scans a slice of uints.
func nus(n int) []uint {
	a := make([]uint, n)
	for i := 0; i < n; i++ {
		a[i] = nu()
	}
	return a
}

// nfs scans a slice of float64s.
func nfs(n int) []float64 {
	a := make([]float64, n)
	for i := 0; i < n; i++ {
		a[i] = nf()
	}
	return a
}

type KMP struct {
	table []int
	p     string
	sz    int
}

func NewKMP(pattern string) *KMP {
	sz := len(pattern)
	table := make([]int, sz+1)
	table[0] = -1
	j := -1
	for i := 0; i < sz; i++ {
		for j >= 0 && pattern[i] != pattern[j] {
			j = table[j]
		}
		j++
		if i+1 < sz && pattern[i+1] == pattern[j] {
			table[i+1] = table[j]
		} else {
			table[i+1] = j
		}
	}
	return &KMP{
		table: table,
		p:     pattern,
		sz:    sz,
	}
}

func (kmp *KMP) FindFrom(t string) []int {
	n := len(t)
	k := 0
	var positions []int
	for i := 0; i < n; i++ {
		for k >= 0 && kmp.p[k] != t[i] {
			k = kmp.table[k]
		}
		k++
		if k >= kmp.sz {
			positions = append(positions, i-kmp.sz+1)
			k = kmp.table[k]
		}
	}
	return positions
}

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)

	solve()
}

func solve() {
	s := ns()
	n := ni()

	ans := 0
	for i := 0; i < n; i++ {
		t := ns()
		kmp := NewKMP(t)
		ans += len(kmp.FindFrom(s))
	}
	println(ans)
}
0