KMP算法入门题集

POJ  2406

题意：求最长循环节

题解：Next数组的使用，判断 len/ (len-Next[len])， 注意Next[] != 0要特别判断一下； 

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

const int maxn=1e6+5;
int Next[maxn], m, n;
char x[maxn], y[maxn];


void KMP_Pre()
{
    int i=0, j=-1;
    Next[0]=-1;
    while(i<m)
    {
        while(j!=-1 && x[i]!=x[j])
            j=Next[j];
        Next[++i]=++j;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt", "r", stdin);
    while(cin>>x, x[0]!='.')
    {
        m=strlen(x);
        int ans=1;
        KMP_Pre();
        if(m%(m-Next[m])==0)
            ans=m/(m-Next[m]);
        cout<<ans<<endl;
    }
    return 0;
}

HDU 3746

题意: 补齐循环节，求最少添加多少个字符，能获得循环节

题解：画个图看看就行了，可发现 (len+x)/ (len+x-（Next[len] +x）) 注意Next[] != 0要特别判断一下；

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

const int maxn=1e6+5;
int Next[maxn], m, n;
char x[maxn], y[maxn];


void KMP_Pre()
{
    int i=0, j=-1;
    Next[0]=-1;
    while(i<m)
    {
        while(j!=-1 && x[i]!=x[j])
            j=Next[j];
        Next[++i]=++j;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt", "r", stdin);
    int T; cin>>T;
    while(T--)
    {
        cin>>x;
        m=strlen(x);
        KMP_Pre();
        int ans;
        if(Next[m]!=0 && m%(m-Next[m])!=0)
            ans=(m-Next[m])-m%(m-Next[m]);
        else if(Next[m]==0)
            ans=m;
        else
            ans=0;
        cout<<ans<<endl;
    }
    return 0;
}

HDU 1358

题意：求前缀的循环节

题解：和前面一样直接判断取余后是否有余数即可

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

const int maxn=1e6+5;
int Next[maxn], m, n;
char x[maxn], y[maxn];

void KMP_Pre()
{
    int i=0, j=-1;
    Next[0]=-1;
    while(i<m)
    {
        while(j!=-1 && x[i]!=x[j])
            j=Next[j];
        Next[++i]=++j;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt", "r", stdin);
    int kase=0;
    while(cin>>m, m)
    {
        cin>>x;
        KMP_Pre();
        printf("Test case #%d
", ++kase);
        for(int i=2; i<=m; i++)
        {
            if(Next[i]>0 && i%(i-Next[i])==0)
                printf("%d %d
", i, i/(i-Next[i]));
        }
        printf("
");
    }
    return 0;
}

HDU 2087 

题意：求子串在母串出现的次数（不重叠）

题解：每次匹配完成后讲j指向0即可

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

const int maxn=1e5+5;
int Next[maxn], m, n;
char x[maxn], y[maxn];


void KMP_Pre()
{
    int i=0, j=-1;
    Next[0]=-1;
    while(i<m)
    {
        while(j!=-1 && x[i]!=x[j])
            j=Next[j];
        Next[++i]=++j;
    }
}

int KMP_Count()
{
    int i=0, j=0;
    int ans=0;
    KMP_Pre();
    while(i<n)
    {
        while(j!=-1 && y[i]!=x[j])
            j=Next[j];
        i++; j++;
        if(j>=m){
            ans++; j=0;
        }
    }
    return ans;
}


int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt", "r", stdin);
    while(cin>>y>>x, y[0]!='#')
    {
        m=strlen(x);
        n=strlen(y);
        cout<<KMP_Count()<<endl;
    }
    return 0;
}

POJ 2752 

题意：求既是前缀又是后缀的子串长度 ； 

题解：这题比之前的要难一点，这个是非常清晰Next数组和KMP算法的过程； 

Next数组记录的就是前缀串，若Next[len]==s[len-1] 即前后缀相等，然后不断迭代Next[len]并判断即可，然后判断s[next[next[n-1]]] == s[n-1]是否成立，这样一直回滚，直到next[next[.....next[n-1]]] == -1为止。

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

const int maxn=1e6+5;
int Next[maxn], m, n;
char x[maxn], y[maxn];


void KMP_Pre()
{
    int i=0, j=-1;
    Next[0]=-1;
    while(i<m)
    {
        while(j!=-1 && x[i]!=x[j])
            j=Next[j];
        Next[++i]=++j;
    }
}

int ans[maxn];
int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt", "r", stdin);
    while(cin>>x)
    {
        m=strlen(x);
        KMP_Pre();
        int pre=m-1, cnt=1;
        while(pre!=-1)
        {
            if(x[pre]==x[m-1])
                ans[cnt++]=pre+1;
            pre=Next[pre];
        }

        while(--cnt)
            cout<<ans[cnt]<<" ";
        cout<<endl;
    }
    return 0;
}

POJ 3080

题意：找多个串之间的公共子串，输出最大的（数据量很小）

题解：暴力截取+KMP匹配判断，维护一个最大的即可； 

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

string str[100], s[100];
int Next[100];

void KMP_Pre(string x, int m)
{
    int i=0, j=-1;
    Next[0]=-1;
    while(i<m)                           // 这个之前错写成j<m
    {
        while(j!=-1 && x[i]!=x[j])
            j=Next[j];
        Next[++i]=++j;
    }
}

bool KMP(string x, int m, string y, int n)
{
    //KMP_Pre(x, m);
    int i=0, j=0;
    while(i<n)
    {
        while(j!=-1 && y[i]!=x[j])
            j=Next[j];
        ++i; ++j;
        if(j>=m)
            return true;
    }
    return false;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    
    int T; cin>>T;
    while(T--)
    {
        int num; cin>>num;
        for(int i=0; i<num; i++)
            cin>>str[i];

        string ans="";
        for(int len=1; len<=str[0].size(); len++)         //这个等于之前丢了...        
            for(int i=0; i+len<=str[0].size(); i++)
            {
                bool flag=1;
                string p=str[0].substr(i, len);
                KMP_Pre(p, p.size());
                for(int k=1; k<num; k++)
                    if( !KMP(p, p.size(), str[k], str[k].size()) ){
                        flag=0; break;
                    }
                if(flag)
                {
                    if(ans.size()<p.size())
                        ans=p;
                    else if(ans.size()==p.size())
                        ans=min(ans,p);                    
                }
            }
        if(ans.size()<3)
            cout<<"no significant commonalities"<<endl;
        else
            cout<<ans<<endl;

    }
    return 0;
}