KMP

kmp

void getnx(string str,int *nx)

{

int len=str.length();int i=0,k=-1;nx[0]=-1;

while(i<len)if(k==-1||str[i]==str[k])nx[++i]=++k;else k=nx[k];

}

int index(string str,string p)

{

int i=0,j=0;int len1=str.length(),len2=p.length();

if(len1==1&&len2==1)if(str[0]==p[0])return 0;else return -1;

int nx[N];getnx(p,nx);

while(i<len1&&j<len2)

if(j==-1||str[i]==p[j])i++,j++;else j=nx[j];

if(j==len2)return i-len2;else return -1;

}

int Count(string str,string p)

{

int ans=0,i=0,j=0;int nx[N];

int len1=str.length(),len2=p.length();

if(len1==1&&len2==1)if(str[0]==p[0])return 1;else return 0;

getnx(p,nx);

for(i=0;i<len1;i++)

{

    while(j>0&&str[i]!=p[j])j=nx[j];

    if(str[i]==p[j])j++;

    if(j==len2)ans++,j=nx[len2];

}

return ans;

}

exkmp

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=50001;

int nxt[maxn],ex[maxn];

void GETNEXT(char *str)

{

int i=0,j,po,len=strlen(str);

nxt[0]=len;

while(str[i]==str[i+1]&&i+1<len)

i++;

nxt[1]=i;

po=1;

for(i=2;i<len;i++)

{

    if(nxt[i-po]+i<nxt[po]+po)

    nxt[i]=nxt[i-po];

    else

    {

        j=nxt[po]+po-i;

        if(j<0)j=0;

        while(i+j<len&&str[j]==str[j+i])

        j++;

        nxt[i]=j;

        po=i;

    }

}

}

void EXKMP(char *s1,char *s2)

{

int i=0,j,po,len=strlen(s1),l2=strlen(s2);

GETNEXT(s2);

while(s1[i]==s2[i]&&i<l2&&i<len)

i++;

ex[0]=i;

po=0;

for(i=1;i<len;i++)

{

    if(nxt[i-po]+i<ex[po]+po)

    ex[i]=nxt[i-po];

    else

    {

        j=ex[po]+po-i;

        if(j<0)j=0;

        while(i+j<len&&j<l2&&s1[j+i]==s2[j])

        j++;

        ex[i]=j;

        po=i;

    }

}

}

©著作权归作者所有：来自51CTO博客作者qinXpeng的原创作品，如需转载，请注明出处，否则将追究法律责任