AcWing 831. KMP字符串
原题链接
简单
作者:
浮云游子意
,
2022-12-01 09:04:05
,
所有人可见
,
阅读 200
golang版本
package main
import (
"bufio"
"fmt"
"os"
)
/*
S[N] 比较长的串
P[M] 比较短的串
# 下标从1开始
for int i :=1 ;i<=n;i++
for j:=1;j<=m;j++
bool flag = true
*/
const (
N = 100010
M = 1000010
)
var (
//s 是原数组 p 是模板数组
p [N]byte
ne [N]int
s [M]byte
n, m int
s1, s2 string
)
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
fmt.Fscan(in, &n, &s1, &m, &s2)
for i := 0; i < n; i++ {
p[i+1] = s1[i]
}
for i := 0; i < m; i++ {
s[i+1] = s2[i]
}
//求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
}
//kmp匹配的过程
for i, j := 1, 0; i <= m; i++ {
//判断不合法那么就让j变成下一个合法的ne[j]
for j > 0 && s[i] != p[j+1] {
j = ne[j]
}
if s[i] == p[j+1] {
j++
}
//合法情况
if j == n {
fmt.Fprintf(out, "%d ", i-n)
//j跳转到下一个满足情况的ne[j]
j = ne[j]
}
}
}