KMP板子

之前花了很多时间都没有弄懂KMP的原理，今天又花了一下午去看KMP的资料总算弄懂了，还A了KMP的板子，开森~

所以特地保存一下板子……

其实我主要是卡在了next数组的构建上面。

这里借用rxz神犇的一张图片（害我还真是看rxz巨佬的博客才弄懂kmp）

宣传一波

这里next数组失配了。我们想要找到这样一个位置 $i$，使得 $[0,i]$ 这个串等于 $[x-i-1,x-1]$ 这个串。因为只有这样才有可能匹配成功（但不一定匹配成功）那么这就相当于要找A的前缀等于B的相同长度的后缀，要求这个长度尽量大。那么，根据next数组的定义，很显然这就是 $nxt[p[now]-1]$。

话不多说直接放板子了qaq（此代码能够AC P3375 【模板】KMP字符串匹配）

#include <cstdio>
#include <cstring>

char s[1000005], p[1000005];
int nxt[1000005];

int main() {
	int now(0), n, m;
	scanf("%s\n%s", s + 1, p + 1);
	n = strlen(s + 1), m = strlen(p + 1);
	nxt[1] = 0;
	for (int x = 2; x <= m;) 
		if (p[now + 1] == p[x]) nxt[x ++] = ++ now;
		else if (now) now = nxt[now];
		else nxt[x ++] = 0;
	for (int i = 1, j = 1; i <= n;) {
		if (s[i] == p[j]) ++ i, ++ j;
		else if (j != 1) j = nxt[j - 1] + 1;
		else ++ i;
		if (j > m) printf("%d\n", i - m), j = nxt[j - 1] + 1;
	}
	for (int i(1); i <= m; ++ i) printf("%d ", nxt[i]);
	return 0;
}