太久没用过都忘记了, 重新写了一遍, 加上了注释
O(n+m) O ( n + m )
#include <bits/stdc++.h> using namespace std; const int MAXP = 100, MAXT = 100000; int nxt[MAXP];//nxt[i]:=p[0~i-1]的最长相同前后缀(p[0~nxt[i]-1] == p[i-nxt[i]~i-1]) char t[MAXT], p[MAXP];//p为模式串, t为目标串 //非优化版本 void init_nxt(char p[]) { int pl = strlen(p); nxt[0] = -1;//nxt[0]为-1 int j=0, k=-1; while(j<pl) {//现在正在比较p[j]位置的后缀, k表示p[j]之前的公共前后缀长度 if(k==-1 || p[j]==p[k]) nxt[++j] = ++k; else k = nxt[k];//失配寻找更短的公共前后缀进行比较 } } ************************************************ *********************************************** 优化版本(kmp数组不再具有公共前后缀长度的意义, 而仅仅是失配后可以跳到的位置) //void init_nxt(char p[]) //{ // int pl = strlen(p); // nxt[0] = -1; // int j=0, k=-1; // while(j<pl) // { // if(k==-1 || p[j]==p[k]) // { // if(p[++j] == p[++k]) nxt[j] = nxt[k];//比上一个版本只多了这一句, // else nxt[j] = k; // kmp失配时回到公共前后缀后面 // //如果失配字符和公共前后缀后面那个字符相同 // //继续匹配立即失配, 所以寻找更短的一个公共前后缀 // } // else k = nxt[k]; // } //} //len-nxt[len]为字符串循环节长度(如果能整除字符串长度) && kmp[len] != 0, kmp[len]=0时说明不循环(相当于循环节长度为len循环一次) int kmp(char t[], char p[]) { int tl = strlen(t); int pl = strlen(p); int i=0, j=0; while(i<tl && j<pl) { if(j==-1 || t[i]==p[j]) ++i, ++j;//第一个字符就失配了(p从第一个字符开始, t前进一个字符) || 匹配成功(两个都前进一个字符) else j=nxt[j]; //失配后p从j前面一个字符的公共前后缀(p[0~nxt[j]-1]==p[j-nxt[j]~j-1]), 下一个位置(p[nxt[j]])开始继续比较 } return j==pl ? i-j : -1;//没有匹配-1, 匹配到返回匹配开始的位置 } int main() { char t[] = "abcaabbccabcdeab"; char p[] = "abbabbabbabbabb"; init_nxt(p); for(int i=0; p[i-1]!='\0'; ++i) cout << nxt[i] << " "; cout << endl; cout << kmp(t, p); return 0; }KMP 算法（1）：如何理解 KMP
O(n+m) O ( n + m ) 感觉不太常用
#include <bits/stdc++.h> using namespace std; const int MAXN = 1E6; int nxt[MAXN], ex[MAXN]; //ex[i]:=S[i~s_len-1]与T最长公共前缀长度 //nxt[i]:=T[i~t_len-1]与T最长公共前缀长度 void init_nxt(char s[]) { int len = strlen(s); nxt[0] = len; int a, p;//匹配成功字符最远位置p, 及这次匹配起始位置a for(int i=0, j=-1; i<len; ++i, --j)//j为p与i的距离 { if(j<0 || i+nxt[i-a]>=p) { if(j<0) p=i, j=0;//如果j<0(i大于p), 从头开始比较 while(p<len && s[p]==s[j]) ++p, ++j; nxt[i] = j; a = i; } else nxt[i] = nxt[i-a]; } } void init_ex(char s1[], char s2[]) { init_nxt(s2); int a, p; int l1 = strlen(s1), l2 = strlen(s2); for(int i=0, j=-1; i<l1; ++i, --j) { if(j<0 || i+nxt[i-a]>=p) { if(j<0) p=i, j=0; while(p<l1 && j<l2 && s1[p]==s2[j]) ++p, ++j; ex[i] = j; a = i; } else ex[i] = nxt[i-a]; } } int main() { char s1[] = "abcdabcdcbcbcd"; char s2[] = "bcd"; init_ex(s1, s2); cout << s1 << endl; for(int i=0; i<strlen(s1); ++i) cout << ex[i]; cout << endl; return 0; }扩展 KMP 算法 拓展kmp算法总结
