作者：jostree 轉載請注明出處 http://www.cnblogs.com/jostree/p/4403560.html
所謂KMP算法，就是判斷一個模式串是否是一個字元串的子串，通常的算法當模式串失配後需要回溯原串和模式串，原串從上次開始比對的下一個字母開始來比對模式串的第一個字母。舉一個例子，原串為ABABABCD，模式串為ABABCD，如圖1一直從頭開始比對，當比對到第5個紅色字母時，發現A和C失配，通常的算法需要回溯原串從第二個字元開始，模式串從第一個字元開始重新比對，如圖2所示：
圖2 傳統方法回溯
我們發現，回溯原串是不必要的，因為我們可以發現，回溯到圖二的情況時一定會失配，原因是在圖1中模式串的前兩個字母已經和原串的前兩個字母比對，并且模式串的前兩個字母不同，是以當模式串第一個字母和原串的字母一定失配，那麼我們就沒有必要去回溯原串，隻需把模式串向右移動就行了。那麼向右移動到什麼位置呢？如圖3所示，我們發現模式串的字首深紅色的AB與模式串失配的第5個字元C之前的綠色字尾AB完全相同，有因為綠色的模式串字尾AB與原串比對，是以我們可以斷定模式串的字首AB一定可以和原串綠色的AB相比對，進而直接可以把模式串向後移動兩位，得到圖4的樣子，繼續進行比對。
圖4 KMP算法失配後向右移動兩位
那麼我們如何計算模式串每次移動的位置呢，對于模式串的每一位我們都要預處理出一個其失配後需要移動到的位置，即next數組，其中next數組第i位的含義為：模式串開始到第i位之前的字元串的字首字元串與字尾字元串相同的最大長度，并另next[0]=-1。進而我們可以口算出ABABCD的next數組：
表1 口算next數組
| 模式串 | A | B | C | D | ||
| 字首字尾比對 | 無 | 字首A=字尾A | 字首AB=字尾AB | |||
| next | -1 | 1 | 2 |
多算幾個模式串的next數組我們就會發現，我們可以利用前面的字母的next數組的值來計算目前字母的next數組，例如對與ABABCD中的第5個字母C，因為他的前一個字母B的next數組的值為1也就是說第1個字首字母A和B的字尾字母A相同，我們并不需要再次進行比較，而是直接比較p[4]與p[next[4]]是否相同我們發現都是B，進而第5個字元C的next數組的值就等于其前一個字母B的next數組值+1。如果不比對怎麼辦？我們隻需再次向前比較p[4]與p[next[next[4]]即可，一直到相等或者next數組的值為-1。這樣我們就可以很輕松的計算next數組了。
其計算next數組和KMP比對的代碼如下，其中KMP函數傳回模式串與原串比對的次數：
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <vector>
5 #include <limits.h>
6 #include <iostream>
7
8 using namespace std;
9 vector<int> GetNext(string p)
10 {
11 vector<int> next;
12 next.push_back(-1);
13 int k = -1;
14 int j = 0;
15 while(j < p.size())
16 {
17 if( k == -1 || p[j] == p[k] )
18 {
19 ++k;
20 ++j;
21 next.push_back(k);
22 }
23 else
24 {
25 k = next[k];
26 }
27 }
28 return next;
29 }
30
31 int KMP(string p, string s, vector<int> next)
32 {
33 int i = 0;
34 int j = 0;
35 int res = 0;
36 while( i < s.size() )
37 {
38 if( j == p.size() )
39 {
40 res++;
41 j = next[j];
42 }
43 else if( j == -1 || s[i] == p[j] )
44 {
45 i++;
46 j++;
47 }
48 else
49 {
50 j = next[j];
51 }
52 }
53 if( s[i] == p[j] )
54 {
55 res++;
56 }
57 return res;
58 }
59
60 int main(int argc, char *argv[])
61 {
62 int n;
63 cin>>n;
64 while( n-- )
65 {
66 string p;
67 string o;
68 cin>>p>>o;
69 vector<int> next = GetNext(p);
70 cout<<KMP(p, o, next)<<endl;
71 }
72 } View Code
next數組的優化：使用這種方法計算next數組時我們會發現一個問題，例如對于模式串為ABAB，原串為ABACABAB的字元串。我們可以得到模式串的next數組為-1，0，0，1。進而當其進行比對第一次失配時如圖5所示，根據失配的第4個B的next值為1，進而模式串下标為1的字母B與原串再次比對，如圖6所示：
圖5 失配
圖6 模式串下标為1的字母B與其進行比對
我們可以發現，這次的比對一定使失敗的，因為在我們的模式串的下标為3的字母B，其p[3]=p[next[3]]='B'，有因為p[3]與原串失配，是以p[next[3]]也一定與原串失配，是以我們在構造模式串時，需要判斷p[i]是否與p[next[i]]相等，如果不想等，指派next即可，如果相等，則需要把對next[next[i]的值賦給next[i]，對于這個例子，因為p[3]=p[next[3]]='B'，是以另next[3]=next[next[3]] = -1。即可得到優化後的next數組。為-1，0，0，-1。
代碼如下：
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <vector>
5 #include <limits.h>
6 #include <iostream>
7
8 using namespace std;
9 vector<int> GetNext(string p)
10 {
11 vector<int> next;
12 next.push_back(-1);
13 int k = -1;
14 int j = 0;
15 while(j < p.size())
16 {
17 if( k == -1 || p[j] == p[k] )
18 {
19 ++k;
20 ++j;
21 if( p[j] != p[k] )
22 {
23 next.push_back(k);
24 }
25 else
26 {
27 next.push_back(next[k]);
28 }
29 }
30 else
31 {
32 k = next[k];
33 }
34 }
35 return next;
36 }
37
38 int KMP(string p, string s, vector<int> next)
39 {
40 int i = 0;
41 int j = 0;
42 int res = 0;
43 while( i < s.size() )
44 {
45 if( j == p.size() )
46 {
47 res++;
48 j = next[j];
49 }
50 else if( j == -1 || s[i] == p[j] )
51 {
52 i++;
53 j++;
54 }
55 else
56 {
57 j = next[j];
58 }
59 }
60 if( s[i] == p[j] )
61 {
62 res++;
63 }
64 return res;
65 }
66
67 int main(int argc, char *argv[])
68 {
69 int n;
70 cin>>n;
71 while( n-- )
72 {
73 string p;
74 string o;
75 cin>>p>>o;
76 vector<int> next = GetNext(p);
77 cout<<KMP(p, o, next)<<endl;
78 }
79 }