模板1：
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int next[10];int nextval[10];void getnext(char *p,int next[]){ int plen=strlen(p); next[0]=-1; int k=-1; int j=0; while(j<plen-1) { if(k==-1||p[j]==p[k]) next[++j]=++k; else k=next[k]; }}//優化后的next數組，不能允許p[j]=p[next[j]]void getnextval(char *p,int nextval[]){ int plen=strlen(p); nextval[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]) nextval[j]=k; else nextval[j]=nextval[k]; } else k=nextval[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=next[j]; } if(j==plen) return i-j;//模式串第一次在文本串中出現的位置 else return -1;}int main(){ char ch[10]; char s[50]; while(cin>>ch>>s) { getnext(ch,next); getnextval(ch,nextval); for(int i=0;i<strlen(ch);i++) { cout<<next[i]<<" "; } cout<<endl; for(int i=0;i<strlen(ch);i++) { cout<<nextval[i]<<" "; } cout<<endl; cout<<kmp(s,ch)<<endl; } return 0;}模板2：
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int fail[30];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 *s,char *p){ int slen=strlen(s); int plen=strlen(p); int j=0;//當前結點編號 for(int i=0;i<slen;i++)//文本串當前指針 { while(j&&p[j]!=s[i])//順著失配邊走，直到可以匹配 j=fail[j]; if(p[j]==s[i]) j++; if(j==plen) { cout<<"find at position "<<i-plen+1<<endl; j=fail[j]; } }}int main(){ char ch[30]; char s[50]; while(cin>>ch>>s) { getfail(ch); for(int i=0;i<=strlen(ch);i++) { cout<<fail[i]<<" "; } cout<<endl; kmp(s,ch); } return 0;}新聞熱點
疑難解答
