AcWing 831. KMP字符串-golang
原题链接
简单
作者:
一只鱼
,
2021-09-03 14:47:31
,
所有人可见
,
阅读 213
AcWing 831. KMP字符串-golang
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
var scan *bufio.Scanner
func main() {
scan = bufio.NewScanner(os.Stdin)
bs := make([]byte, 1000*1024)
scan.Buffer(bs, len(bs))
n, _ := strconv.Atoi(readLine())
// 使得下标从1开始方便使用
p := " " + readLine()
m, _ := strconv.Atoi(readLine())
s := " " + readLine()
ne := make([]int, n+2)
// 求 next 数组的过程
for i, j := 2, 0; i <= n; i++ {
for j > 0 && p[i] != p[j+1] {
j = ne[j]
}
if p[i] == p[j+1] {
j++
}
ne[i] = j
}
res := make([]string, 0, n)
// KMP 匹配的过程,i 枚举的是当前 s
// j 每次从0开始往前走,判断 j 是否继续走
for i, j := 1, 0; i <= m; i++ {
for j > 0 && s[i] != p[j+1] {
// 不能继续走,就先退一步
j = ne[j]
}
if s[i] == p[j+1] {
j++
}
if j == n {
res = append(res, strconv.FormatInt(int64(i-n), 10))
j = ne[j]
}
}
fmt.Println(strings.Join(res, " "))
}
func readLine() string {
scan.Scan()
return scan.Text()
}