有些東西不專(zhuān)門(mén)記一下就要忘。。。

kmp

核心是 \(next\) 數(shù)組, 即當(dāng)前綴的除去自身的最大 \(border\) 。在字符串匹配時(shí)考慮雙指針，一旦失配就跳 \(next\)，找到可能再次匹配的開(kāi)始位置 \(p\) 。基于 \(border\) 的性質(zhì)，只要 \(s[i - j + 1, i]\) 與 \(t[1, j]\) 匹配，\(s[p, i]\) 與 \(s[i - j + (i - p + 1), i]\) 相等。首先對(duì) \(t\) 自己進(jìn)行匹配，求 \(next_p\) 的時(shí)候用已經(jīng)求出的 \(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數(shù)組很有用，所以kmp是很有必要學(xué)的，當(dāng)然字符串題實(shí)在不行就hash。

ACAM