kmp算法的最难理解的是next数组的生成，next数组存储的是匹配子串数组前缀与后缀相同长度。该next数组长度为字符串+1，next[0] = -1。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; class KMP { private: char *str,*tar; int slen,tlen; int *next; private: void getNext() { int i=0,k=-1; next[0] = -1; //后一位保存着前一位的值 while(i < tlen) if(k==-1 || tar[i]==tar[k]) next[++i] = ++k; else k = next[k]; } public: KMP(char *s,char *t) { slen = strlen(s); tlen = strlen(t); str = new char[slen+1]; //末尾 多一个字节 tar = new char[tlen+1]; next = new int[(tlen+1)*sizeof(int)]; strcpy(str,s); strcpy(tar,t); getNext(); } ~KMP() { if(str){delete str;str = NULL;} if(tar){delete tar;tar = NULL;} if(next){delete next;next = NULL;} } int getIndex() { int i=0,j=0; while(i < slen && j < tlen) if(j == -1 || str[i] == tar[j]) ++i,++j; else j = next[j]; if(j==tlen) return i - j; else return -1; } int getCount() { int i=0,j=0,cnt = 0; for(;i<slen;++i) { if(j > 0 && str[i] != tar[j]) j = next[j]; if(str[i] == tar[j]) ++j; if(j == tlen) { j = next[j]; ++cnt; } } return cnt; } }; int main() { char s[100],t[100]; while(~scanf("%s%s",s,t)) { KMP kmp(s,t); printf("%d %d ",kmp.getIndex(),kmp.getCount()); } return 0; }
例题：
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; #define N (2*100000+10) int Next[N]; void makeNext(char *Pat) { int len = strlen(Pat); int k = 0; Next[0] = 0; for(int i=1;i<len;++i) { if(k > 0 && Pat[i] != Pat[k]) k = Next[k-1]; if(Pat[i] == Pat[k]) ++k; Next[i] = k; } } int Kmp(char *str,char *Pat) { int len = strlen(str),Patlen = strlen(Pat); if(len < Patlen) return -1; string temp = str; temp += str; strcpy(str,temp.c_str()); len = strlen(str); for(int i=0,j=0;i+Patlen < len;) { for(;j<Patlen;++j) if(str[i+j] != Pat[j]) break; if(j >= Patlen) return i; i = i + Next[j] + 1; j = Next[j]; } return -1; } int main() { char str1[N],str2[N]; while(~scanf("%s%s",str1,str2)) { printf("%s ",Kmp(str1,str2)!=-1?"yes":"no"); } return 0; }
给两个字符串，第一个前缀与第二个后缀相同，求最大len与输出相同部分字符。
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> using namespace std; #define N (100000+10) int Next[N]; void getNext(char *str) { int len = strlen(str); memset(Next,0,sizeof(Next)); int i=0,k=-1; Next[0] = -1; while(i < len) if(k==-1 || str[i] == str[k]) Next[++i] = ++k; else k = Next[k]; } int main() { char str[N],tar[N/2]; while(~scanf("%s%s",str,tar)) { int slen = strlen(str),tlen = strlen(tar); strcat(str,tar); getNext(str); int k = Next[strlen(str)]; while(k > slen || k > tlen) k = Next[k]; if(k) printf("%s ",tar+(tlen-k)); printf("%d ",k); } return 0; }
KMP+dp
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MOD (10007) int *Next; int len; void getIndex(char* str) { int i=0,k=-1; Next[0] = -1; while(i < len) if(k==-1 || str[i] == str[k]) Next[++i] = ++k; else k = Next[k]; } int getCount(char* str) { int i=0,j=0,cnt = 0; for(;i<len;++i) { if(j>0 && str[i] != str[j]) j = Next[j]; if(str[i]==str[j]) ++j,cnt = (cnt+1)%MOD; } return cnt%MOD; } int main() { int t; scanf("%d",&t); while(t--) { char *str; scanf("%d",&len); str = new char[len+1]; Next = new int[(len+1)*sizeof(int)]; scanf("%s",str); getIndex(str); int dp[len+1]; dp[0] = 0; int sum = 0; for(int i=1;i<=len;++i) { dp[i] = (dp[Next[i]] + 1)%MOD; sum = (sum + dp[i])%MOD; } printf("%d ",sum); delete str; delete Next; str = NULL; Next = 0; } return 0; }
hdu1358（不太理解的题目）
#include<iostream> #include<cstdio> #include<cstring> using namespace std; class KMP { private: char *str,*tar; int *next; int slen,tlen; private: void getNext() { if(tlen == 0) return; int i=0,k=-1; next[i] = k; while(i < tlen) if(k==-1 || tar[i]==tar[k]) next[++i] = ++k; else k = next[k]; } public: KMP(char *s,char *t) { slen = strlen(s); tlen = strlen(t); next = new int[(tlen+1)*sizeof(int)]; str = new char[slen+1]; tar = new char[tlen+1]; strcpy(str,s); strcpy(tar,t); getNext(); } ~KMP() { if(next){delete next;next = NULL;} if(str){delete str;str = NULL;} if(tar){delete tar;tar = NULL;} } void showNext() { if(tlen == 0) return; printf("next: "); for(int i=0;i<=tlen;++i) printf("%d ",next[i]); printf(" "); } void showAns() { for(int i=1;i<=slen;++i) if(i%(i-next[i])==0 && i/(i-next[i])> 1) printf("%d %d ",i,i/(i-next[i])); } int getIndex() { int i=0,j=0; while(i < slen && j < tlen) { if(j==-1 || str[i] == tar[j]) ++i,++j; else j = next[j]; } if(j == tlen) return i-j; else return -1; } int getCount() { int i=0,j=0,ans=0; for(;i<slen;++i) { while(j > 0 && str[i] != tar[j]) j = next[j]; if(str[i] == tar[j]) ++j; if(j == tlen) { ++ans; j = next[j]; } } return ans; } }; int main() { char *str; int n; int t = 0; while(~scanf("%d",&n),n) { str = new char[n+1]; scanf("%s",str); KMP kmp(str,str); printf("Test case #%d ",++t); kmp.showAns(); if(str){delete str;str = NULL;} printf(" "); } return 0; } /* aaaa aaa */