字符串算法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
char s1[N],s2[N];
ll n1,n2,nt[N],f[N];
int main(){
	cin >> (s1+1) >> (s2+1);
	n1=strlen(s1+1),n2=strlen(s2+1);
	for(ll i=2,j=0;i<=n2;i++){
		while(j>0&&s2[i]!=s2[j+1])j=nt[j];
		if(s2[i]==s2[j+1])j++;
		nt[i]=j;
	}
	for(ll i=1,j=0;i<=n1;i++){
		while(j>0&&(j==n2||s1[i]!=s2[j+1]))j=nt[j];
		if(s1[i]==s2[j+1])j++;
		f[i]=j;
	}
	for(ll i=1;i<=n1;i++)if(f[i]==n2)cout << i-n2+1 << endl;
	for(ll i=1;i<=n2;i++)cout << nt[i] << ' ';
	return 0;
}