KMP模板（更新）

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAXN=1e6+5; char pat[MAXN],txt[MAXN]; int fail[MAXN]; //若模式串p的前i个字符组成的子串为s //那么s的前fail[i]个字符与s的后fail[i]个字符相同 //字符串都是从下标1开始的 //求解fail的过程，就是模式串与自己匹配的过程 //O(len(p)) void getfail(char *p) { int plen=strlen(p+1); fail[1]=0;//递推初值 for(int j=0,i=2;i<=plen;++i) { while(j>0&&p[j+1]!=p[i]) j=fail[j]; if(p[j+1]==p[i]) j++; fail[i]=j; } } //O(len(p)+len(t)) int kmp(char *t,char *p) { int tlen=strlen(t+1),plen=strlen(p+1); int sum=0; int j=0;//number of characters matched for(int i=1;i<=tlen;i++)//scan the text from left to right { while(j>0&&p[j+1]!=t[i]) j=fail[j];//next character does not match if(p[j+1]==t[i]) j++;//next character matches if(j==plen) { sum++; printf("find at position %d\n",i-plen+1); j=fail[j];//all of p matched, look for the next match } } return sum; } int main() { while(scanf("%s%s",pat+1,txt+1)!=EOF) { getfail(pat); int plen=strlen(pat+1); for(int i=1;i<=plen;++i) printf("%d ",fail[i]); printf("\n"); printf("%d\n",kmp(txt,pat)); // int cycle=plen-fail[plen]; // if(plen%cycle==0) printf("%d\n",plen/cycle); // else printf("1\n"); } return 0; } /* aababaab baaababaabbaabb a a b a b a a b 0 1 0 1 0 1 2 3 */

KMP（非最大长度版本）

模板1：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int fail[10]; int failval[10]; void getfail(char *p,int fail[]) { int plen=strlen(p); fail[0]=-1; int k=-1; int j=0; while(j<plen-1) { if(k==-1||p[j]==p[k]) fail[++j]=++k; else k=fail[k]; } } //优化后的fail数组，不能允许p[j]=p[fail[j]] void getfailval(char *p,int failval[]) { int plen=strlen(p); failval[0]=-1; int k=-1; int j=0; while(j<plen-1) { if(k==-1||p[j]==p[k]) { ++j;++k; if(p[j]!=p[k]) failval[j]=k; else failval[j]=failval[k]; } else k=failval[k]; } } //kmp的整体时间复杂度为O(m+n),m和n分别为模式串和文本串的长度 int kmp(char *s,char *p) { int i=0,j=0; int slen=strlen(s),plen=strlen(p); while(i<slen&&j<plen) { if(j==-1||s[i]==p[j]) i++,j++; else j=fail[j]; } if(j==plen) return i-j;//模式串第一次在文本串中出现的位置 else return -1; } int main() { char ch[10]; char s[50]; while(cin>>ch>>s) { getfail(ch,fail); getfailval(ch,failval); for(int i=0;i<strlen(ch);i++) { cout<<fail[i]<<" "; } cout<<endl; for(int i=0;i<strlen(ch);i++) { cout<<failval[i]<<" "; } cout<<endl; cout<<kmp(s,ch)<<endl; } return 0; }

abbaaba 0 0 0 0 1 1 2 模板2：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAXN=1e5+5; //patar a[8]={"abcdefg"}; char pat[MAXN],txt[MAXN]; int fail[MAXN]; void getfail(char *p) { int plen=strlen(p); fail[0]=0,fail[1]=0;//递推初值 for(int i=1;i<plen;++i) { int j=fail[i]; while(j&&p[i]!=p[j]) j=fail[j]; if(p[i]==p[j]) fail[i+1]=j+1; else fail[i+1]=0; } } void kmp(char *t,char *p) { int tlen=strlen(t),plen=strlen(p); int j=0;//当前结点编号 for(int i=0;i<tlen;++i)//文本串当前指针 { //顺着失配边走，直到可以匹配 while(j&&p[j]!=t[i]) j=fail[j]; if(p[j]==t[i]) ++j; if(j==plen) { cout<<"find at position "<<i-plen+1<<endl; j=fail[j]; } } } int main() { while(cin>>pat>>txt) { getfail(pat); int plen=strlen(pat); for(int i=0;i<=plen;++i) cout<<fail[i]<<" "; cout<<endl; kmp(txt,pat); } return 0; }

定义文本串 txt t x t ，模式串 pat p a t