主体思路
使用KMP算法
比起双指针朴素算法,kmp的特点就是“在匹配失败后,模式串的指针知道下一步能跳到哪里”
而记录模式串指针往哪里跳的数组,就是大名鼎鼎的next数组
该数组里放着的下标j,是能满足“在字符串上s[1 … j] = s[i - j + 1 … i]”
后面能匹配前面的最长后缀长度 == 模式串与字符串匹配失败后模式串能匹配下去的最小移动距离
注意细节
所用到的字符串要前面加” “
基本代码
package main
import (
"fmt"
"os"
"bufio"
)
const N = 100010
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewReader(os.Stdin)
ne [N]int
n, m int
s, p string
)
func main() {
fmt.Fscan(in, &n, &p, &m, &s)
p = " " + p; s = " " + s // kmp算法从1开始,因此两个串前都要加个空格
for i, j := 2, 0; i <= n; i++ { // 先对模式串进行预处理
for j > 0 && p[i] != p[j + 1] {j = ne[j]} // 两字符串错开; 匹配失败后,j快速跳到ne[j](跳过某些会重复匹配的字符),继续匹配
if p[i] == p[j + 1] {j++} // 匹配成功,j移动
ne[i] = j // 标记next数组
}
for i, j := 1, 0; i <= m; i++ { // 正式匹配
for j > 0 && s[i] != p[j + 1] {j = ne[j]} // 两字符串错开; 匹配失败后,j快速跳到ne[j](跳过某些会重复匹配的字符),继续匹配
if s[i] == p[j + 1] {j++} // 匹配成功,j移动
if j == n { // 匹配完成
fmt.Fprintf(out, "%d ", i - n)
j = ne[j] // 这时,j还得要跳一次
}
}
out.Flush()
}