参考博客: https://wenku.baidu.com/view/8e9ebefb0242a8956bece4b3.html
http://www.cnblogs.com/Rlemon/archive/2013/06/26/3157574.html
代码:
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 6 const int MAXN = 1e5 + 10; 7 char str1[MAXN], str2[MAXN]; //str1为主串,str2为模式串 8 int exnext[MAXN], extend[MAXN], n, m; 9 10 void get_exnext(void){ 11 exnext[0] = m; 12 int j = 0, k = 1; //k是使p最大的i 13 while(j + 1 < m && str2[j] == str2[j + 1]) j++; 14 exnext[1] = j; 15 for(int i = 2; i < m; i++){ 16 int p = exnext[k] + k - 1; //p为当前匹配最远的位置 17 int l = exnext[i - k]; //[k,p]匹配[0,exnext[k]-1],所以[i,p]匹配[i-k,exnext[k]-1],[i-k,i-k+l]匹配[0,l] 18 if(i + l < p + 1) exnext[i] = l; 19 else{ 20 j = max(0, p - i + 1); 21 while(i + j < m && str2[i + j] == str2[j]) j++; 22 exnext[i] = j; 23 k = i; 24 } 25 } 26 } 27 28 void ex_kmp(void){ 29 get_exnext(); 30 int j = 0, k = 0; 31 while(j < n && j < m && str1[j] == str2[j]) j++; 32 extend[0] = j; 33 for(int i = 1; i < n; i++){ 34 int p = extend[k] + k - 1; 35 int l = exnext[i - k]; 36 if(i + l < p + 1) extend[i] = l; 37 else{ 38 j = max(0, p - i + 1); 39 while(i + j < n && j < m && str1[i + j] == str2[j]) j++; 40 extend[i] = j; 41 k = i; 42 } 43 } 44 } 45 46 int main(void){ 47 scanf("%s%s", str1, str2); 48 n = strlen(str1); 49 m = strlen(str2); 50 ex_kmp(); 51 for(int i = 0; i < m; i++){ 52 cout << exnext[i] << " "; 53 } 54 cout << endl; 55 for(int i = 0; i < n; i++){ 56 cout << extend[i] << " "; 57 } 58 cout << endl; 59 return 0; 60 }