[数据结构]KMP小结

2022-01-19 07:17:50

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 1000005
int next[N];

void getnext(char *s)
{
    int i,j,len=strlen(s);
    next[0]=j=-1;
    for(i=1;i<len;i++)
    {
        while(j>=0&&s[j+1]!=s[i])
            j=next[j];
        if(s[i]==s[j+1])
            j++;
        next[i]=j;
    }
}

int main()
{
    int i,len;
    char s[N];
    while(scanf("%s",s)!=EOF&&s[0]!=‘.‘)
    {
        getnext(s);
        len=strlen(s);
        if(next[len-1]!=-1&&len%(len-1-next[len-1])==0)
            printf("%d\n",len/(len-1-next[len-1]));
        else
            printf("1\n");
    }
    return 0;
}

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 100005
int Next[N];

void getnext(char *s)
{
    int i,j,len=strlen(s);
    Next[0]=j=-1;
    for(i=1;i<len;i++)
    {
        while(j>=0&&s[j+1]!=s[i])
            j=Next[j];
        if(s[j+1]==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-1]==-1) printf("%d\n",L);
        else 
        {
            m=L-1-Next[L-1];
            d=Next[L-1]+1;  // (d+x)==0(mod m)
            printf("%d\n",(m-d%m)%m);
        }
    }
    return 0;
}

HDU 3746

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

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

# define N 200005
int Next[N];

void getnext(char *s)
{
    int i,j,len=strlen(s);
    Next[0]=j=-1;
    for(i=1;i<len;i++)
    {
        while(j>=0&&s[j+1]!=s[i])
            j=Next[j];
        if(s[j+1]==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=0;
        L1=strlen(s1),L2=strlen(s2);
        strcat(s1,s2);
        getnext(s1);
        len=L1+L2;
        if(Next[len-1]==-1||len%(len-1-Next[len-1]))
            printf("0\n");
        else
        {
            int m=len-1-Next[len-1];
            if(L1%m||L2%m) 
                printf("0\n");
            else
            {
                for(i=m;i<=L1&&i<=L2;i+=m)
                    if(L1%i==0&&L2%i==0)
                        ans++;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

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 10007
# define N 200005
int Next[N];
int num[N];

void getnext(char *s)
{
    int i,j,len=strlen(s);
    Next[0]=j=-1;
    for(i=1;i<len;i++)
    {
        while(j>=0&&s[j+1]!=s[i])
            j=Next[j];
        if(s[j+1]==s[i])
            j++;
        Next[i]=j;
    }
}

int main()
{
    int T,len,i,ans;
    char s[N];
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        memset(num,0,sizeof(num));
        scanf("%d%s",&len,s);
        getnext(s);
        for(i=len-1;i>=0;i--)
        {
            num[i]++;
            if(num[i]>=MOD) 
                num[i]-=num[i]/MOD*MOD;
            if(Next[i]!=-1) 
            {
                num[Next[i]]+=num[i];
                if(num[Next[i]]>=MOD)
                    num[Next[i]]%=MOD;
            }
            ans=(ans+num[i])%MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}

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 100005
char s1[N],s2[N];
int Next[N];

void getnext(char *s)
{
    int i,j,len=strlen(s);
    Next[0]=j=-1;
    for(i=1;i<len;i++)
    {
        while(j>=0&&s[j+1]!=s[i])
            j=Next[j];
        if(s[j+1]==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-1;
    /*    for(i=0;i<=pos;i++)
            printf("%d ",Next[i]);*/
        ans=-1;
        while(pos!=-1)
        {
            if(Next[pos]!=-1&&Next[pos]<L1&&L2-(Next[pos]+1)>=0)
            {
                ans=Next[pos];
                break;
            }
            pos=Next[pos];
        }
        if(ans==-1) printf("0\n");
        else
        {
            for(i=0;i<=ans;i++) printf("%c",s1[i]);
            printf(" %d\n",ans+1);
        }
    }
    return 0;
}

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 1000005
int a[N],b[N];
int Next[N];

void getnext(int x[],int n)
{
    int i,j;
    Next[0]=j=-1;
    for(i=1;i<n;i++)
    {
        while(j>=0&&x[j+1]!=x[i])
            j++;
        if(x[j+1]==x[i])
            j++;
        Next[i]=j;
    }
}

int kmp(int a[],int n,int b[],int m)
{
    int i,j=-1;
    getnext(b,m);
    for(i=0;i<n;i++)
    {
        while(j>=0&&b[j+1]!=a[i])
            j=Next[j];
        if(a[i]==b[j+1])
            j++;
        if(j+1==m)
            return i-m+2;
    }
    return -1;
}

int main()
{
    int T,n,m,i;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<m;i++)
            scanf("%d",&b[i]);
        int ans=kmp(a,n,b,m);
        printf("%d\n",ans);
    }
    return 0;
}

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 200005
int Next[N];

void getnext(char *s)
{
    int i,j,len=strlen(s);
    Next[0]=j=-1;
    for(i=1;i<len;i++)
    {
        while(j>=0&&s[j+1]!=s[i]) j=Next[j];
        if(s[j+1]==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=-1;
    for(i=0;i<len;i++)
    {
        while(j>=0&&ch[j+1]!=s[i]) j=Next[j];
        if(ch[j+1]==s[i]) j++;
        if(j+1==m) ans.push_back(i-m+1);
    }
    return ans;
}

KMP模板

5.总结:

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

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

[数据结构]KMP小结

码农公寓

相关文章