kmp 算法基本思路
1.初始化 j = -1，表示 pattern 当前已被匹配的最后位。
2.让 i 遍历文本串 text，对每个 i，执行 3、4来试图匹配 text[i] 和 pattern[j + 1]。
3.直到 j 回退到 -1 或者是 text[i] == pattern[j + 1]，否则不断令 j = next[j]。
4.如果 text[i] == pattern[j + 1]，则令 j ++。如果 j 达到 pattern_len - 1，说明 pattern 是 text 的子串。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int N = 100010,M = 100010; 5 6 int n,m; 7 char p[N],s[M]; 8 int ne[N]; 9 10 int main() 11 { 12 cin >> n >> p + 1 >> m >> s + 1; 13 14 //求next的过程 15 for (int i = 2,j = 0; i <= n; i ++ ) 16 { 17 while(j && p[i] != p[j + 1]) j = ne[j]; //令j 退回 18 if(p[i] == p[j + 1]) j ++; //如果匹配成功，令前后缀变长 + 1; 19 ne[i] = j; // p[1,j] == p[l - i + 1,i]; 20 } 21 22 //kmp 匹配过程 23 for (int i = 1,j = 0; i <= m; i ++ ) 24 { 25 while(j && s[i] != p[j + 1]) j = ne[j]; 26 if(s[i] == p[j + 1]) j ++; 27 if(j == n) //匹配成功 28 { 29 printf("%d ",i - n); 30 j = ne[j]; // 31 } 32 } 33 return 0; 34 }
