记录编号	558437	评测结果	AAAAAAAAAA
题目名称	kmp模板	最终得分	100
用户昵称	tat	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-12-30 22:09:14	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
int next[1919810]={0};
queue<int> ans; 
string s1,s2; 
char s3[1919810];
int main(int argc, char** argv) {
	freopen("kmp.in","r",stdin); 
	freopen("kmp.out","w",stdout);
	//init
	cin>>s1>>s2;
	for(int i=0;i<s2.length();i++){
		s3[i]=s2[i];
	}
	s3[s2.length()]='?';
	for(int i=s2.length()+1;i<=s1.length()+s2.length();i++){
		s3[i]=s1[i-s2.length()-1];
	}
	int l=s1.length()+s2.length()+1;//字符串长度 
	int j=0;//f(i-1)的大小 
	//finish
	for(int i=1;i<l;i++){
		while(j!=0&&s3[i]!=s3[j]){
			j=next[j-1];//j是指f(i-1)的大小，j-1是指下标 
		}
		if(s3[i]==s3[j]){
			j++;
		}
		next[i]=j;
		//cout<<j<<' ';
		if(next[i]==s2.length()){//当前缀函数长等于s2.l 
			ans.push(i-2*s2.length()+1);
		}
	}
	while(!ans.empty()){
		cout<<ans.front()<<endl;
		ans.pop();
	}
	for(int i=0;i<s2.length();i++){
		cout<<next[i]<<' ';
	}
	return 0;
}