KMP模板

poj3461

/*输出所有出现的位置、出现次数 */
#include<iostream>
#include<cstring>   
using namespace std;
string s,t;
int ans; 
int next[100000];
int slen,tlen;
int main()
{
    cin>>s>>t;
    slen=s.length(),tlen=t.length();
    int j,k;j=0,k=-1;
    next[0]=-1;
    while(j<tlen)
    {
        if(k==-1||t[j]==t[k])
        {
            k++,j++;
            next[j]=k;
        }
        else k=next[k];
    }
    int i;
    j=0,i=0;
    while(i<slen)
    {
        if(j==-1||s[i]==t[j])i++,j++;
        else j=next[j];
        if(j==tlen)
        {
            cout<<i-tlen<<' ';
            ans++;
        }
    }
    cout<<endl<<ans;
    return 0;
}

/*另一种,在别人的代码中看见的，然而并不能看懂。。。难以理解，不举荐*/

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

const int N = 1000002;
int next[N];
char S[N], T[N];
int slen, tlen;

void getNext()
{
    int j, k;
    j = 0; k = -1; next[0] = -1;
    while(j < tlen)
        if(k == -1 || T[j] == T[k])
            next[++j] = ++k;
        else
            k = next[k];

}
/*
返回模式串T在主串S中首次出现的位置
返回的位置是从0开始的。
*/
int KMP_Index()
{
    int i = 0, j = 0;
    getNext();

    while(i < slen && j < tlen)
    {
        if(j == -1 || S[i] == T[j])
        {
            i++; j++;
        }
        else
            j = next[j];
    }
    if(j == tlen)
        return i - tlen;
    else
        return -1;
}
/*
返回模式串在主串S中出现的次数
*/
int KMP_Count()
{
    int ans = 0;
    int i, j = 0;

    if(slen == 1 && tlen == 1)
    {
        if(S[0] == T[0])
            return 1;
        else
            return 0;
    }
    getNext();
    for(i = 0; i < slen; i++)
    {
        while(j > 0 && S[i] != T[j])
            j = next[j];
        if(S[i] == T[j])
            j++;
        if(j == tlen)
        {
            ans++;
            j = next[j];
        }
    }
    return ans;
}
int main()
{
    
    int TT;
    int i, cc;
    cin>>TT;
    while(TT--)
    {
        cin>>T>>S;
        slen = strlen(S);
        tlen = strlen(T);
        cout<<"模式串T在主串S中首次出现的位置是: "<<KMP_Index()<<endl;
        cout<<"模式串T在主串S中出现的次数为: "<<KMP_Count()<<endl;
    }
    return 0;
}
 

/*lrh*/
#include<iostream>
#include<cstdio>
#include<cstring>


using namespace std;
int next[100010];
char p[10010],s[1000010];
int t,num,l1,l2;

void get_next()
{
    int j=0;
    int k=-1;
    next[0]=-1;
    while(j<l2)
    {
        if(k==-1||p[k]==p[j])
        {
            k++;
            j++;
            next[j]=k;
        }
        else
        {
            k=next[k];
        }
    }
}

int kmp()
{
    int i=0;
    int j=0;
    get_next();
    while(i<l1)
    {
        if(j==-1||p[j]==s[i])
        {
            j++;
            i++;
        }
        else 
        {
            j=next[j];
        }
        if(j==l2) 
        {
            cout<<i-l2+1<<endl;
            j=next[j];
        }
    }
}

int main()
{
    t=1;
    while(t--)
    {
        num=0;
        cin>>s>>p;
        l1=strlen(s);
        l2=strlen(p);
        get_next();
        kmp();
        for(int i=1;i<=l2;i++)cout<<next[i]<<' ';
    }
}

/*myl*/
#include<iostream>
#include<cstring>   
using namespace std;
string s,t;
//int ans; 
int next[100000];
int slen,tlen;
int main()
{
    cin>>s>>t;
    slen=s.length(),tlen=t.length();
    int j,k;j=0,k=-1;
    next[0]=-1;
    while(j<tlen)
    {
        if(k==-1||t[j]==t[k])
        {
            k++,j++;
            next[j]=k;
        }
        else k=next[k];
    }
    int i;
    j=0,i=0;
    while(i<slen)
    {
        if(j==-1||s[i]==t[j])i++,j++;
        else j=next[j];
        if(j==tlen)
        {
            cout<<i-tlen+1<<endl;
            j=next[j];
            //ans++;
        }
    }
    for(int i=1;i<=tlen;i++)
    cout<<next[i]<<' ';
    return 0;
}