kmp算法专题总结

next数组的含义：next[i]表示以字符串s的第i个字符为结尾的后缀与s前缀匹配的长度

next数组也可以当做fail数组，即当模式串s[j]与串t[i]不匹配时，只要将j转换到next[j]继续匹配即可

　　在求s的next数组时，也用同样的原理，当s[j]与s[i]不匹配时，只要将j转换到next[j]继续匹配即可，当注意此时模式串的首字母是s[0]

poj3461

//next[i]表示和模式串第i位匹配失败时，再去和模式串第next[i]位匹配

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

char s[],t[];

int tot,nxt[];

void kmp_pre(){

    int i,j;

    int len=strlen(s);

    j=nxt[]=-;i=;

    while(i<len){

        while(j!=- && s[i]!=s[j]) j=nxt[j];

            nxt[++i]=++j;

    }

}

void kmp(){

    int i,j,ans;

    int m=strlen(s);

    int n=strlen(t);

    i=j=ans=;

    while(i<n){

        while(j!=- && t[i]!=s[j]) j=nxt[j];

        ++i,++j;

        if(j==m){

            ans++;

            j=nxt[j];

        }

    }

    printf("%d\n",ans);

}

int main(){

    int tt;

    scanf("%d",&tt);

    while(tt--){

        memset(nxt,,sizeof nxt);

        scanf("%s%s",s,t);

        kmp_pre();

        kmp();

    }

}

hdu1711 求最左边匹配位

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define maxn 1000005

int nxt[maxn],a[maxn],b[maxn],n,m;

void kmp_pre(){

    memset(nxt,,sizeof nxt);

    int i,j;

    i=;j=nxt[]=-;

    while(i<m){

        while(j!=- && b[i]!=b[j])j=nxt[j];

            nxt[++i]=++j;

    }

}

void kmp(){

    int i,j,ans;

    i=j=ans=;

    while(i<n){

        while(j!=- && a[i]!=b[j])j=nxt[j];

            ++i;++j;

        if(j==m){

            printf("%d\n",i-j+);

            return;

        }

    }

    puts("-1");

    return;

}

int main(){

    int t;

    cin >> t;

    while(t--){

        scanf("%d%d",&n,&m);

        for(int i=;i<n;i++)scanf("%d",&a[i]);

        for(int i=;i<m;i++)scanf("%d",&b[i]);

        kmp_pre();

        kmp();

    }

}

poj1961 求循环节

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define maxn 1000005

int m,nxt[maxn];

char s[maxn];

void kmp_pre(){

    memset(nxt,,sizeof nxt);

    int i,j;

    i=;j=nxt[]=-;

    while(i<m){

        while(j!=- && s[i]!=s[j])j=nxt[j];

            nxt[++i]=++j;

    }

}

int main(){

    int tt=;

    while(scanf("%d",&m),m){

        printf("Test case #%d\n",++tt);

        scanf("%s",s);

        kmp_pre();

        for(int i=;i<=m;i++){

            if(i%(i-nxt[i])== && i/(i-nxt[i])>)

                printf("%d %d\n",i,i/(i-nxt[i]));

        }

        puts("");

    }

}

poj2406 求最小循环节

//如果将s数组右移一维，那么nxt[i]就是：后缀s[i]与s前缀匹配的长度

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define maxn 1000005

int m,nxt[maxn];

char s[maxn];

void kmp_pre(){

    memset(nxt,,sizeof nxt);

    m=strlen(s);

    int i,j;

    i=;j=nxt[]=-;

    while(i<m){

        while(j!=- && s[i]!=s[j])j=nxt[j];

            nxt[++i]=++j;

    }

}

int main(){

    while(scanf("%s",s)&&strcmp(s,".")){

        kmp_pre();

        int ans=;

        if(m%(m-nxt[m])==)ans=m/(m-nxt[m]);

        printf("%d\n",ans);

    }

}

hdu3336 next数组+线性dp

//cnt[i]表示以s[i]结尾的串可以匹配的前缀数

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define mod 10007

#define maxn 200005

int m,t,nxt[maxn];

char s[maxn];

void kmp_pre(){

    memset(nxt,,sizeof nxt);

    int i,j;

    i=;j=nxt[]=-;

    while(i<m){

        while(j!=- && s[i]!=s[j])j=nxt[j];

            nxt[++i]=++j;

    }

}

int main(){

    scanf("%d",&t);

    while(t--){

        scanf("%d%s",&m,s);

        kmp_pre();

        int ans=,cnt[maxn]={};

        cnt[]=,cnt[]=;

        for(int i=;i<=m;i++)

            cnt[i]=(cnt[nxt[i]]+)%mod;

        for(int i=;i<=m;i++)ans=(ans+cnt[i])%mod;

        printf("%d\n",ans);

    }

}

*hdu3746 循环节应用

/*

最小循环节=串长-末位匹配长度

*/#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define maxn 100005

int nxt[maxn],m;

char s[maxn];

void pre_kmp(){

    memset(nxt,,sizeof nxt);

    m=strlen(s);

    int i,j;

    i=;j=nxt[]=-;

    while(i<m){

        while(j!=- && s[i]!=s[j])j=nxt[j];

            nxt[++i]=++j;

    }

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%s",s);

        pre_kmp();

        if(nxt[m]==)printf("%d\n",m);

        else if(m%(m-nxt[m])==)puts("");

        else {

            int cir=m-nxt[m];

            printf("%d\n",cir-nxt[m]%cir);

        }

    }

}

*hdu2594 后缀套后缀

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define maxn 50005

char s1[maxn<<],s2[maxn<<];

int n,m,nxt[maxn<<];

void kmp_pre(){

    memset(nxt,,sizeof nxt);

    int len=strlen(s1);

    int i=,j=-;

    nxt[]=-;

    while(i<len){

        while(s1[i]!=s1[j] && j!=-)

            j=nxt[j];

        nxt[++i]=++j;

    }

}

int main(){

    while(~scanf("%s%s",s1,s2)){

        n=strlen(s1);

        m=strlen(s2);

        int minlen=min(n,m);

        strcat(s1,s2);

        kmp_pre();

        int len=strlen(s1),ans=nxt[len];

        if(ans==){

            printf("0\n");

            continue;

        }

        else {

            while(ans>minlen)

                ans=nxt[ans];

            char tmp[maxn]={};

            strncpy(tmp,s1,ans);

            printf("%s %d\n",tmp,ans);

        }

    }

    return ;

}

巴特西

kmp算法专题总结

最新文章

热门文章