扩展KMP

https://segmentfault.com/a/1190000008663857
 1 /**
 2  *
 3  * author 刘毅（Limer）
 4  * date   2017-03-12
 5  * mode   C++
 6  */
 7 #include<iostream>
 8 #include<string>
 9 using namespace std;
10 
11 /* 求解T中next[]，注释参考GetExtend() */
12 void GetNext(string T, int next[])
13 {
14     int t_len = T.size();
15     next[0] = t_len;
16     int a;
17     int p;
18 
19     for (int i = 1, j = -1; i < t_len; i++, j--)
20     {
21         if (j < 0 || i + next[i - a] >= p)
22         {
23             if (j < 0)
24                 p = i, j = 0;
25 
26             while (p < t_len&&T[p] == T[j])
27                 p++, j++;
28 
29             next[i] = j;
30             a = i;
31         }
32         else
33             next[i] = next[i - a];
34     }
35 }
36 
37 /* 求解extend[] */
38 void GetExtend(string S, string T, int extend[], int next[])
39 {
40     GetNext(T, next);  //得到next
41     int a;             
42     int p;             //记录匹配成功的字符的最远位置p，及起始位置a
43     int s_len = S.size();
44     int t_len = T.size();
45 
46     for (int i = 0, j = -1; i < s_len; i++, j--)  //j即等于p与i的距离，其作用是判断i是否大于p（如果j<0，则i大于p）
47     {
48         if (j < 0 || i + next[i - a] >= p)  //i大于p（其实j最小只可以到-1，j<0的写法方便读者理解程序），
49         {                                   //或者可以继续比较（之所以使用大于等于而不用等于也是为了方便读者理解程序）
50             if (j < 0)
51                 p = i, j = 0;  //如果i大于p
52 
53             while (p < s_len&&j < t_len&&S[p] == T[j])
54                 p++, j++;
55 
56             extend[i] = j;
57             a = i;
58         }
59         else
60             extend[i] = next[i - a];
61     }
62 }
63 
64 int main()
65 {
66     int next[100] = { 0 };
67     int extend[100] = { 0 };
68     string S = "aaaaabbb";
69     string T = "aaaaac";
70 
71     GetExtend(S, T, extend, next);
72 
73     //打印next和extend
74     cout << "next:    " << endl;
75     for (int i = 0; i < T.size(); i++)
76         cout << next[i] << " ";
77 
78     cout << "
extend:  " << endl;
79     for (int i = 0; i < S.size(); i++)
80         cout << extend[i] << " ";
81     cout << endl;
82     return 0;
83 }