kmp模板

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;
}