现在的位置: 首页 > 综合 > 正文

KMP 小结

2019年02月09日 ⁄ 综合 ⁄ 共 3217字 ⁄ 字号 评论关闭

看了这位大神的博客:http://www.cnblogs.com/wuyiqi/archive/2012/01/05/2313746.html

花了一个上午的时间把题都A了,对KMP的前缀与后缀,以及循环节问题有了一定的了解。特别是next[]数组,可以记录前缀和后缀相同的长度,如果这个长度没有超过一半的话,就可以求字符串的循环节n-next[n]。

先附下KMP模版:

void getnext()
{
    int i=0,j=-1;
    next[i]=j;
    while(i<m)
    {
        while(j>=0&&b[i]!=b[j]) j=next[j];
        i++;j++;
        next[i]=j;
    }
}
void KMP()
{
    int i=0,j=0;
    while(i<n)
    {
        while(j>=0&&a[i]!=b[j]) j=next[j];
        i++;j++;
        if(j==m)
        {
            report(i-j);
            j=next[j];
        }
    }
}

下面是一些hdu题的代码:

hdu3336:

题意:求给定字符串的所有子串中含前缀的数量

这里用了dp的思想,当前状态能够通过当前的最大前缀的前缀数量+1得来。

dp[i]表示以s[i]结尾并且必须包含第i个位置的子串中是前缀的数量。

以i结尾,首先包含从1到i这整个子串作为一个前缀,然后计算从1-i这个子串中是前缀的数量。j=next[i]到i之间已经不含以s[i]结尾的字符串了,又因为s[0]-s[j-1]==s[i-j]-s[i-1],,所以d[i]还要加上dp[j],即后缀中可能是前缀的子串数。

dp[i]=dp[next[i]]+1;

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstdio>
#include<cstring>
#define maxn 200005
#define INF 0xfffffff
#define MOD 10007
using namespace std;
int n;
char s[maxn];
int next[maxn];//next[i]=j表示与s[0-j]与s[i-j--i]相等
int dp[maxn];//dp[i]表示i之前的的前缀之和
void getnext()
{
    int i=0,j=-1;
    next[i]=j;
    while(i<n)
    {
        while(j>=0&&s[i]!=s[j]) j=next[j];
        i++;j++;
        next[i]=j;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>s;
        getnext();
        dp[0]=0;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            dp[i]=dp[next[i]]+1;
            sum=(sum+dp[i])%MOD;
        }
        cout<<sum<<endl;
    }
	return 0;
}

hdu3746

题意:求最少需要在结尾后面补几个字符才能凑成两个循环.

这就是一个典型的求循环节的问题,只要求出循环节,再判断当前字符串的长度和循环节的大小关系就能得出答案。

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstdio>
#include<cstring>
#define maxn 100005
#define INF 0xfffffff
using namespace std;
char s[maxn];
int n,next[maxn];
void getnext()
{
    int i=0,j=-1;
    next[i]=j;
    while(i<n)
    {
        while(j>=0&&s[i]!=s[j]) j=next[j];
        i++;j++;
        next[i]=j;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%s",s);
        n=strlen(s);
        getnext();
        //cout<<0<<endl;
        int m=n-next[n];//循环节长度

        if(n==m)
        {
            printf("%d\n",m);
            continue;
        }
        //cout<<n-2*next[n]<<endl;
        if(n%m==0)
        printf("0\n");
        else
        printf("%d\n",m-n%m);
    }
	return 0;
}

hdu2087

题意:从一个字符串中最多能出现多少个匹配串。

这里只要把每次打到匹配串的长度之后,j开始的位置指向0就行了。

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstdio>
#include<cstring>
#define maxn 2005
#define INF 0xfffffff
using namespace std;
int ans;
int next[maxn];
char a[maxn],b[maxn];//模式串为b
int n,m;
void getnext()
{
    int i=0,j=-1;
    next[i]=j;
    while(i<m)
    {
        while(j>=0&&b[i]!=b[j]) j=next[j];
        i++;
        j++;  
        next[i]=j;
    }
}
void KMP()
{
    int i=0,j=0;
    while(i<n)
    {
        while(j>=0&&a[i]!=b[j]) j=next[j];
        //cout<<i<<' '<<j<<endl;
        i++;j++;
        if(j==m)
        {
            ans++;
            //cout<<i<<' '<<j<<endl;
            j=0;
        }
    }
}
int main()
{
    while(cin>>a)
    {
        if(a[0]=='#')
        break;
        cin>>b;
        n=strlen(a),m=strlen(b);
        //cout<<n<<' '<<m<<endl;
        getnext();
        /*
        for(int i=0;i<=m;i++)
        {
            cout<<i<<' '<<next[i]<<endl;
        }
        */

        ans=0;
        KMP();
        cout<<ans<<endl;

    }
    return 0;
}

hdu2594

题目:求最长的a的前缀同时满足是b的后缀

这里直接把b串连在a串后面,然后用kmp跑一次,最后判断next[n+m]的大小。因为无论是前缀还是后缀,都是a,b的子串,所以应该比a,b的长度要小,所以用循环来不断套next[]。

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstdio>
#include<cstring>
#define maxn 50005
#define INF 0xfffffff
using namespace std;
char a[maxn*2],b[maxn];
int next[maxn*2];
int n,m,ans;
void getnext()
{
    int i=0,j=-1;
    next[i]=j;
    while(i<n+m)
    {
        while(j>=0&&a[i]!=a[j]) j=next[j];
        i++;
        j++;
        next[i]=j;
    }
    ans=next[n+m];
    while(ans>n)//后缀串要比两个串都要短
    {
        ans=next[ans];
    }
    while(ans>m)
    {
        ans=next[ans];
    }
}
int main()
{
    while(scanf("%s",a)!=EOF)
    {
        scanf("%s",b);
        n=strlen(a),m=strlen(b);
        for(int i=n;i<n+m;i++)
        {
            a[i]=b[i-n];
        }
        a[n+m+1]='\0';
        getnext();
        if(ans==0)
        cout<<ans<<endl;
        else
        {
            for(int i=0;i<ans;i++)
            {
                cout<<a[i];
            }
            cout<<' ';
            cout<<ans<<endl;
        }
    }
	return 0;
}

抱歉!评论已关闭.