luogu3375 【模板】KMP字符串匹配

nxt数组下标从1开始而a，b数组下标从0开始。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int lena, lenb, nxt[1000005];
char a[1000005], b[1000005];
void mknxt(){
	int j=0, k;
	k = nxt[0] = -1;
	while(j<lenb){
		if(k==-1 || b[j]==b[k])	nxt[++j] = ++k;
		else	k = nxt[k];
	}
}
void kmp(){
	int i=0, j=0;
	while(i<lena){
		if(j==-1 || a[i]==b[j])	i++, j++;
		else	j = nxt[j];
		if(j==lenb)	printf("%d
", i-j+1), j = nxt[j];
	}
}
int main(){
	scanf("%s %s", a, b);
	lena = strlen(a);
	lenb = strlen(b);
	mknxt();
	kmp();
	for(int i=1; i<=lenb; i++)	printf("%d ", nxt[i]);
	return 0;
}