KMP

手动模拟出奇迹

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
	return s*f;
}
const int N=1e6+3;
char a[N],b[N];
int lena,lenb;
int fail[N];
int main(){
	scanf("%s%s",a+1,b+1);
	lena=strlen(a+1);lenb=strlen(b+1);
	int j=0;
	for(int i=2;i<=lenb;++i){
		while(j&&b[j+1]!=b[i]) j=fail[j];
		if(b[j+1]==b[i]) ++j;
		fail[i]=j;
	}
	j=0;
	for(int i=1;i<=lena;++i){
		while(j&&b[j+1]!=a[i]) j=fail[j];
		if(b[j+1]==a[i]) ++j;
		if(j==lenb){
			printf("%d\n",i-lenb+1);
			j=fail[j];
		}
	}
	for(int i=1;i<=lenb;++i) printf("%d ",fail[i]);
	return 0;
}