KMP模板
const int maxn=2000000+50;
int nextt[maxn];
int a[maxn],b[maxn];
int n,m;
int kmnext[maxn];
void Find()
{
memset(nextt,0,sizeof(nextt));
int i=0;
int j=-1;
nextt[0]=-1;
while(i<m)
{
while(j!=-1&&b[i]!=b[j])
{
j=nextt[j];
}
nextt[++i]=++j;
}
}
void EXKMP()
{
int i=0;
int j=-1;
nextt[0]=-1;
while(i<m)
{
if(j!=-1&&b[i]!=b[j])
j=kmnext[j];
if(b[++i]==b[++j])
kmnext[i]=kmnext[j];
else
kmnext[i]=j;
}
}
int KMP()
{
int ans=-1;
int j=-1;
for(int i=0; i<n; i++)
{
while(j!=-1&&a[i]!=b[j])
j=nextt[j];
j++;
if(j==m)
{
ans=i-m+2;
break;
}
if(a[i]==b[j])
{
if(j+1==m)
{
ans=i-m+2;
break;
}
}
}
return ans;
}
