有些东西不专门记一下就要忘。。。
kmp
核心是 \(next\) 数组, 即当前缀的除去自身的最大 \(border\) 。在字符串匹配时考虑双指针，一旦失配就跳 \(next\)，找到可能再次匹配的开始位置 \(p\) 。基于 \(border\) 的性质，只要 \(s[i - j + 1, i]\) 与 \(t[1, j]\) 匹配，\(s[p, i]\) 与 \(s[i - j + (i - p + 1), i]\) 相等。首先对 \(t\) 自己进行匹配，求 \(next_p\) 的时候用已经求出的 \(next_{1 \to p}\) 更新即可。
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 5;
int n, m, nxt[N]; char s1[N], s2[N];
int main() {
scanf("%s %s", s1 + 1, s2 + 1);
n = strlen(s1 + 1), m = strlen(s2 + 1);
for (int i = 2, j = 0; i <= m; ++i) {
while (j && s2[j + 1] != s2[i]) j = nxt[j];
nxt[i] = j += (s2[j + 1] == s2[i]);
}
for (int i = 1, j = 0; i <= n; ++i) {
while (j && s2[j + 1] != s1[i]) j = nxt[j];
if ((j += (s1[i] == s2[j + 1])) == m) {
printf("%d\n", i - m + 1);
j = nxt[j];
}
}
for (int i = 1; i<= m; ++i) {
printf("%d ", nxt[i]);
}
return 0;
}
next数组很有用，所以kmp是很有必要学的，当然字符串题实在不行就hash。