KMP几道入门题目

HDU 1711 Number Sequence（模板题）

#include<stdio.h>
#include<string>
const int maxn=1e6+10;
const int maxm=1e4+10;
int t,n,m,s[maxn],p[maxn];
int next[maxm];
void GetNext()
{
    int plen=0;
    int slen=-1;
    next[0]=-1;
    while(plen<m)
    {
        if(slen==-1||p[plen]==p[slen])
        {
            plen++;slen++;
            if(p[plen]!=p[slen])next[plen]=slen;
            else next[plen]=next[slen];
        }
        else slen=next[slen];
    }
}
int kmp()
{
    int plen=0;
    int slen=0;
    while(plen<m&&slen<n)
    {
        if(plen==-1||p[plen]==s[slen])
        {
            plen++;slen++;
        }
        else plen=next[plen];
    }
    if(plen==m)
    return slen-plen+1;
    else return -1;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%d",&s[i]);
        for(int i=0;i<m;i++)scanf("%d",&p[i]);
        GetNext();
        printf("%d
",kmp());
    }
    return 0;
}

 HDU 2087 剪花布条

求一个串在另一个串中的出现次数，KMP模板题

#include<iostream>
#include<string>
using namespace std;
string s,p;
int plen,slen,Next[1010];
void GetNext()
{
    int j=0;
    int k=-1;
    Next[0]=-1;
    while(j<plen)
    {
        if(k==-1||p[j]==p[k])
        {
            j++;k++;
            if(p[j]!=p[k])Next[j]=k;
            else Next[j]=Next[k];
        }
        else k=Next[k];
    }
}
int kmp()
{
    int j=0;
    int i=0;
    int count=0;
    while(j<plen&&i<slen)
    {
        if(j==-1||p[j]==s[i])
        {
            j++;i++;
        }
        else j=Next[j];
        if(j==plen)
        {
            j=0;
            count++;
        }
    }
    return count;
}
int main()
{
    while(cin>>s&&s[0]!='#')
    {
        cin>>p;
        plen=p.size();
        slen=s.size();
        GetNext();
        printf("%d
",kmp());
    }
    return 0;
} 

 HDU 2594 Simpsons’ Hidden Talents （next函数应用）

#include<iostream>
#include<string.h>
using namespace std;
const int maxn=5e5+10;
char s1[maxn],s2[maxn];
int Next[maxn],len1,len2,ans;
void GetNext()
{
    int k=-1;
    int j=0;
    Next[0]=-1;
    while(j<len1+len2)
    {
        if(k==-1||s1[j]==s1[k])
        {
            j++;k++;Next[j]=k;
        }
        else k=Next[k];
    }
}
int main()
{
    while(~scanf("%s%s",s1,s2))
    {
        len1=strlen(s1);
        len2=strlen(s2);
        strcat(s1,s2);
        GetNext();
        ans=Next[len1+len2];
        while(ans>len1||ans>len2)ans=Next[ans];
        if(ans){
            for(int i=0;i<ans;i++)printf("%c",s1[i]);printf(" %d",ans);printf("
");
        }
        else printf("%d
",ans);
    }
    return 0;
}