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; }

 

洛谷 kmp字符串匹配

/*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; }