字符串模式匹配KMP算法中的next数组算法及C++实现

1. 在串S和串T中分别设置比较的起始下标i和j;
2. 重复下述操作，直到S或T的所有字符均比较完毕;
    2.1 如果S[i]等于T[j]，继续比较S和T的下一对字符;
    2.2 否则将下标j回溯到next[j]的位置，即j = next[j];
    2.3 如果j等于-1，则将下标i和j分别加1，准备下一趟比较;
3. 如果T中所有字符均比较完毕，则返回匹配的i-j;
    否则返回-1;

 1 int KMP(string S, string T)
 2 {
 3     vector<int> next = getNext(T);
 4     int i = 0, j = 0;
 5     while (S[i] != '\0' && T[j] != '\0')
 6     {
 7         if (S[i] == T[j])
 8         {
 9             ++i;
10             ++j;
11         }
12         else
13         {
14             j = next[j];
15         }
16         if (j == -1)
17         {
18             ++i;
19             ++j;
20         }
21     }
22     if (T[j] == '\0')
23         return i - j;
24     else
25         return -1;
26 }

 1 vector<int> getNext(string T)
 2 {
 3     vector<int> next(T.size(), 0);            // next矩阵，含义参考王红梅版《数据结构》p84。
 4     next[0] = -1;                            // next矩阵的第0位为-1
 5     int k = 0;                            // k值
 6     for (int j = 2; j // 从字符串T的第2个字符开始，计算每个字符的next值
 7     {
 8         while (k > 0 && T[j - 1] != T[k])    
 9             k = next[k];
10         if (T[j - 1] == T[k])
11             k++;
12         next[j] = k;
13     }
14     return next;                            // 返回next矩阵
15 }

 1 #include 
 2 #include 
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 vector<int> getNext(string T)
 8 {
 9     vector<int> next(T.size(), 0);            // next矩阵，含义参考王红梅版《数据结构》p84。
10     next[0] = -1;                            // next矩阵的第0位为-1
11     int k = 0;                            // k值
12     for (int j = 2; j // 从字符串T的第2个字符开始，计算每个字符的next值
13     {
14         while (k > 0 && T[j - 1] != T[k])    
15             k = next[k];
16         if (T[j - 1] == T[k])
17             k++;
18         next[j] = k;
19     }
20     return next;                            // 返回next矩阵
21 }
22 
23 int KMP(string S, string T)
24 {
25     vector<int> next = getNext(T);
26     int i = 0, j = 0;
27     while (S[i] != '\0' && T[j] != '\0')
28     {
29         if (S[i] == T[j])
30         {
31             ++i;
32             ++j;
33         }
34         else
35         {
36             j = next[j];
37         }
38         if (j == -1)
39         {
40             ++i;
41             ++j;
42         }
43     }
44     if (T[j] == '\0')
45         return i - j;
46     else
47         return -1;
48 }
49 
50 int main()
51 {
52     string S = "ababaababcb";
53     string T = "ababc";
54     int num = KMP(S, T);
55     cout << num;
56     return 0;
57 }