KMP【模板】

void KMP(string a,string b){
	a='-'+a,
	b='-'+b;
	int n=a.size()-1,m=b.size()-1;
	nex[1]=0;
	for(int i=2,j=0;i<=m;i++){
		while(j>0 && b[i]!=b[j+1]){
			j=nex[j];
		}
		if(b[i]==b[j+1]){
			j++;
		}
		nex[i]=j;
	}
	for(int i=1,j=0;i<=n;i++){
		while(j>0 && b[j+1]!=a[i]){
			j=nex[j];
		}
		if(a[i]==b[j+1]){
			j++;
		}
		if(j==m){
			cout<<i-m+1<<'\n';
			j=nex[j];
		}
	}
}