KMP算法

matrix67大神的算法讲解的太犀利了
http://www.matrix67.com/blog/archives/115
 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <queue>
 5 #include <algorithm>
 6 #include <cstdio>
 7 #include <list>
 8 #include <cstring>
 9 using namespace std;
10 
11 void kmp(char A[], char B[], int P[], int n, int m) {
12     int j = -1; //表示已经匹配的位置
13     for (int i = 0; i < n; i++) {
14         while ((j > -1) && (B[j + 1] != A[i]))
15             j = P[j];
16         if (B[j + 1] == A[i])
17             j = j + 1;
18         if (j == m - 1) {
19             cout << "Pattern occurs with shift:  " << i - m + 1 << endl;
20             j = P[j];
21         }
22     }
23 }
24 
25 void next(int P[], char B[], int m) {
26     P[0] = -1;
27     int j = -1;
28     for (int i = 1; i < m; i++) {
29         while ((j > -1) && (B[j + 1] != B[i])) {
30             j = P[j];
31         }
32         if (B[j + 1] == B[i])
33             j = j + 1;
34         P[i] = j;
35     }
36 }
37 
38 int main() {
39     char src[] = "rock and roll";
40     char zc[] = "and";
41     int p[10];
42 
43     next(p, zc, strlen(zc));
44     for (int i = 0; i < strlen(zc); i++)
45         cout << p[i] << "  ";
46     cout << endl;
47     kmp(src, zc, p, strlen(src), strlen(zc));
48     return 0;
49 }