记录编号	581864	评测结果	AAAAAAAAAA
题目名称	kmp模板	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-08-25 17:55:43	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
//kmp模板 
const int N = 1e6+40;
char a[N],b[N];
int nx[N],f[N];
int main(){
	freopen("kmp.in","r",stdin);
	freopen("kmp.out","w",stdout);
	scanf("%s%s",a+1,b+1);
	int la = strlen(a+1),lb = strlen(b+1);
	for(int i = 2,j = 0;i <= lb;i++){
		while(j > 0 && b[i] != b[j+1])j = nx[j];
		if(b[i] == b[j+1])j++;
		nx[i] = j;
	}
	for(int i = 1,j = 0;i <= la;i++){
		while(j > 0 && (j == lb || a[i] != b[j+1]))j = nx[j];
		if(a[i] == b[j+1])j++;
		f[i] = j;
		if(f[i] == lb)printf("%d\n",i-lb+1);
	}
	for(int i = 1;i <= lb;i++)printf("%d ",nx[i]);
	printf("\n");
	
	return 0;
}