kmp
void getnx(string str,int *nx)
{
int len=str.length();int i=0,k=-1;nx[0]=-1;
while(i } 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 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 { 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 #include #include #include 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 i++; nxt[1]=i; po=1; for(i=2;i { if(nxt[i-po]+i nxt[i]=nxt[i-po]; else { j=nxt[po]+po-i; if(j<0)j=0; while(i+j 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 i++; ex[0]=i; po=0; for(i=1;i { if(nxt[i-po]+i ex[i]=nxt[i-po]; else { j=ex[po]+po-i; if(j<0)j=0; while(i+j j++; ex[i]=j; po=i; } } } ©著作权归作者所有：来自51CTO博客作者qinXpeng的原创作品，如需转载，请注明出处，否则将追究法律责任
