[数据结构]KMP小结

时间：2021-12-01 05:12:47

KMP小结  

By Wine93 2013.9

1.学习链接: http://www.matrix67.com/blog/archives/115

2.个人小结

1.KMP在字符串中匹配中起着巨大作用，可以在O(n+m)内完成

2.要充分理解next 数组,其求法和next数组的含义(最长后缀等于最长前缀),了解其用途，下面我就next数组在求字符串最小周期中的应用举例

(1).什么是字符串最小周期?

Ex:字符串ababab，最小周期为2,为ab

Ex:字符串abcd,最小周期为4,为abcd

(2)最小周期的一个性质

如果len%(len-next[len])==0,则该字符串的最小周期为len-next[len]

(3)性质的证明

[数据结构]KMP小结

欲证：若len%(len-next[len])==0, 则该字符串的最小周期为len-next[len]  (len表示该字符串长度)

证：我们分2部分证

① 若len%(len-next[len])==0，len-next[len]为字符串s的周期  

② 证明len-next[len]就是其最小周期

因为next数组的含义是最长后缀等于最长前缀,所以s[ 1……next[len] ]

和s[next[len]+1……len ]是相等的,如上图，线段(1)和线段(2)相等

因为len%(len-next[len])==0,所以我们把线段(2)可以平均分成很多等份(图中假设为4份),每份长度都为s1,线段(1)也可以分成同等份，如上图，根据next数组的定义,s1=s2,又因为s2=s3,而s3=s4….所以依次类推可得s1=s2=s3=s4=s5=s6=s7=s8,所以，s1是字符串s的周期,所以①得证

若len-next[len]不是其最小周期，也就是说存在更小的长度是字符串s的周期，也就是说next[len]要变大(也就是说最长前缀等于最长后缀的值要增大),而根据next数组的定义，next[len]就是已经是最大值(已经是最长前缀等于最长后缀),所以相互矛盾，所以②得证

综上所述: 如果len%(len-next[len])==0,则该字符串的最小周期为len-next[len] (len表示该字符串长度)

3.相关题目:

(1)循环节相关:

POJ 2406 Period  http://poj.org/problem?id=2406

# include<cstdio>

# include<cstring>

using namespace std;

# define N

int next[N];

void getnext(char *s)

{

    int i,j,len=strlen(s);

    next[]=j=-;

    for(i=;i<len;i++)

    {

        while(j>=&&s[j+]!=s[i])

            j=next[j];

        if(s[i]==s[j+])

            j++;

        next[i]=j;

    }

}

int main()

{

    int i,len;

    char s[N];

    while(scanf("%s",s)!=EOF&&s[]!='.')

    {

        getnext(s);

        len=strlen(s);

        if(next[len-]!=-&&len%(len--next[len-])==)

            printf("%d\n",len/(len--next[len-]));

        else

            printf("1\n");

    }

    return ;

}

POJ 2406

HDU 3746 Cyclic Nacklacehttp://acm.hdu.edu.cn/showproblem.php?pid=3746

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define N

int Next[N];

void getnext(char *s)

{

    int i,j,len=strlen(s);

    Next[]=j=-;

    for(i=;i<len;i++)

    {

        while(j>=&&s[j+]!=s[i])

            j=Next[j];

        if(s[j+]==s[i])

            j++;

        Next[i]=j;

    }

}

int main()

{

    int T,L,pos,m,d;

    char s[N];

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",s);

        getnext(s);

        L=strlen(s);

        if(Next[L-]==-) printf("%d\n",L);

        else

        {

            m=L--Next[L-];

            d=Next[L-]+;  // (d+x)==0(mod m)

            printf("%d\n",(m-d%m)%m);

        }

    }

    return ;

}

HDU 3746

CF 182D Common Divisors http://codeforces.com/problemset/problem/182/D

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define N

int Next[N];

void getnext(char *s)

{

    int i,j,len=strlen(s);

    Next[]=j=-;

    for(i=;i<len;i++)

    {

        while(j>=&&s[j+]!=s[i])

            j=Next[j];

        if(s[j+]==s[i])

            j++;

        Next[i]=j;

    }

}

int main()

{

    int i,len,L1,L2,ans;

    char s1[N],s2[N];

    while(scanf("%s%s",s1,s2)!=EOF)

    {

        ans=;

        L1=strlen(s1),L2=strlen(s2);

        strcat(s1,s2);

        getnext(s1);

        len=L1+L2;

        if(Next[len-]==-||len%(len--Next[len-]))

            printf("0\n");

        else

        {

            int m=len--Next[len-];

            if(L1%m||L2%m)

                printf("0\n");

            else

            {

                for(i=m;i<=L1&&i<=L2;i+=m)

                    if(L1%i==&&L2%i==)

                        ans++;

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

            }

        }

    }

    return ;

}

CF 182D

(2)Next数组:

HDU 3336 Count the string http://acm.hdu.edu.cn/showproblem.php?pid=3336

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define MOD

# define N

int Next[N];

int num[N];

void getnext(char *s)

{

    int i,j,len=strlen(s);

    Next[]=j=-;

    for(i=;i<len;i++)

    {

        while(j>=&&s[j+]!=s[i])

            j=Next[j];

        if(s[j+]==s[i])

            j++;

        Next[i]=j;

    }

}

int main()

{

    int T,len,i,ans;

    char s[N];

    scanf("%d",&T);

    while(T--)

    {

        ans=;

        memset(num,,sizeof(num));

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

        getnext(s);

        for(i=len-;i>=;i--)

        {

            num[i]++;

            if(num[i]>=MOD)

                num[i]-=num[i]/MOD*MOD;

            if(Next[i]!=-)

            {

                num[Next[i]]+=num[i];

                if(num[Next[i]]>=MOD)

                    num[Next[i]]%=MOD;

            }

            ans=(ans+num[i])%MOD;

        }

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

    }

    return ;

}

HDU 3336

HDU 2594 Simpsons’ Hidden Talents  http://acm.hdu.edu.cn/showproblem.php?pid=2594

# include<cstdio>

# include<cstring>

using namespace std;

# define N

char s1[N],s2[N];

int Next[N];

void getnext(char *s)

{

    int i,j,len=strlen(s);

    Next[]=j=-;

    for(i=;i<len;i++)

    {

        while(j>=&&s[j+]!=s[i])

            j=Next[j];

        if(s[j+]==s[i])

            j++;

        Next[i]=j;

    }

}

int main()

{

    int i,L1,L2,pos,ans;

    while(scanf("%s%s",s1,s2)!=EOF)

    {

        L1=strlen(s1),L2=strlen(s2);

        strcat(s1,s2);

        getnext(s1);

        pos=L1+L2-;

    /*    for(i=0;i<=pos;i++)

            printf("%d ",Next[i]);*/

        ans=-;

        while(pos!=-)

        {

            if(Next[pos]!=-&&Next[pos]<L1&&L2-(Next[pos]+)>=)

            {

                ans=Next[pos];

                break;

            }

            pos=Next[pos];

        }

        if(ans==-) printf("0\n");

        else

        {

            for(i=;i<=ans;i++) printf("%c",s1[i]);

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

        }

    }

    return ;

}

HDU 2594

(3)KMP匹配:

HDU 1711 Number Sequence http://acm.hdu.edu.cn/showproblem.php?pid=1711

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define N

int a[N],b[N];

int Next[N];

void getnext(int x[],int n)

{

    int i,j;

    Next[]=j=-;

    for(i=;i<n;i++)

    {

        while(j>=&&x[j+]!=x[i])

            j++;

        if(x[j+]==x[i])

            j++;

        Next[i]=j;

    }

}

int kmp(int a[],int n,int b[],int m)

{

    int i,j=-;

    getnext(b,m);

    for(i=;i<n;i++)

    {

        while(j>=&&b[j+]!=a[i])

            j=Next[j];

        if(a[i]==b[j+])

            j++;

        if(j+==m)

            return i-m+;

    }

    return -;

}

int main()

{

    int T,n,m,i;

    scanf("%d",&T);

    while(T--)

    {

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

        for(i=;i<n;i++)

            scanf("%d",&a[i]);

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

            scanf("%d",&b[i]);

        int ans=kmp(a,n,b,m);

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

    }

    return ;

}

HDU 1711

CF 8A Train and Peter (string::find也可以) http://codeforces.com/problemset/problem/8/A

4.KMP模板

# include<cstdio>

# include<cstring>

# include<vector>

# include<algorithm>

using namespace std;

# define VI vector<int>   //返回所有匹配点

# define N

int Next[N];

void getnext(char *s)

{

    int i,j,len=strlen(s);

    Next[]=j=-;

    for(i=;i<len;i++)

    {

        while(j>=&&s[j+]!=s[i]) j=Next[j];

        if(s[j+]==s[i]) j++;

        Next[i]=j;

    }

}

VI kmp(char *s,char *ch)

{

    int i,j,len=strlen(s),m=strlen(ch);

    VI ans;

    ans.clear();

    getnext(ch);

    j=-;

    for(i=;i<len;i++)

    {

        while(j>=&&ch[j+]!=s[i]) j=Next[j];

        if(ch[j+]==s[i]) j++;

        if(j+==m) ans.push_back(i-m+);

    }

    return ans;

}

KMP模板

5.总结:

KMP的应用很大，一定要深入理解，尤其是next数组, 这对处理字符串匹配问题有着重大影响，AC自动机就是基于KMP来实现的.同时也要理解next数组的局限性(只能是后缀与前缀的对应关系)，这对解题时的判断有着重要作用 

注：后缀数组可以解决KMP的一部*限性

相关文章