一、问题描述：
对于两个字符串S、T，找到T在S中第一次出现的起始位置，若T未在S中出现，则返回-1。
二、输入描述：
两个字符串S、T。
三、输出描述：
字符串T在S中第一次出现的起始位置，若未出现，则返回-1。
四、输入例子：
ababaababcb
ababc
五、输出例子：
5
六、KMP算法解析：
KMP算法分为两步，第一步是计算next数组，第二步是根据next数组通过较节省的方式回溯来比较两个字符串。
网络上不同文章关于next数组的角标含义略有差别，这里取参考文献中王红梅《数据结构(C++版)》的next定义。
设长字符串为S，短字符串为T，next数组的长度与短字符串T的长度一致，next[j]代表使T[0]~T[k-1]=T[j-k]~T[j-1]成立的最大k值。
当T="ababc"时，next=[-1,0,0,1,2]。
通俗的讲，next[j]代表了从0往后查k个字母与从j-1往前查k个字母，这k个字母按角标排列，正好完全一样的最大k值，其作用是减少回溯的距离，从而减少比较次数。
根据《数据结构(C++版)》KMP算法的伪代码可以用如下伪代码表述：
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;
KMP算法的C++代码如下：
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 }
书中只给出next数组的定义，算法留给读者完成，这里我们将其完成。
根据书中next数组的定义，当T="ababc"时，
j=0时，next[0] = -1;
j=1时，next[1] = 0;
接下来的next数组要进行计算，
j=2时，T[0]≠T[1]，则next[2] = 0;
j=3时，由于之前已经比较过T[0]与T[1]不想等，所以无需比较T[0~1]与T[1~2]（一定不想等），直接比较T[0]=T[2]，则next[3] = 1;
j=4时，由于next[3] = 1可知T[0]=T[2]，所以可以直接比较T[1]=T[3]，可得T[0~1]与T[2~3]，则next[4] = 2;
还有一种情况可以节省计算next的时间，这里换一个长一点的字符串说明这种情况，当T="ababaababcb"时，
j=4时，我们计算出next[4] = 2（ab=ab）;
j=9时，我们计算出next[9] = 4（abab=abab）;
j=10时，next[9] = 4可知T[0~3]=T[5~8]，直接比较T[9]='c'和T[4]='a'不相等，由next[4]为2可得T[0-1]和T[2-3]重复为已知、由已经判断到T[9]与T[4]可得T[7-8]和T[2-3]重复为已知，所以可以推断出T[0-1]与T[7-8]为重复字符，可直接判断T[9]与T[next[4]]，即T[9]与T[2]，从而省略重复判断T[0-1]与T[7-8]。
计算next数据的C++代码如下：
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.size(); ++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 }
其中，第8、9行为上述T="ababaababcb"，j=10时出现的情况。第10、11行为类似T[0]=T[2]的比较成功的情况。第12行为类似next[3] = 1的赋值。
七、完整程序
1 #include <iostream>
2 #include <vector>
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.size(); ++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 }
参考文献：
[1]王红梅, 胡明, 王涛. 数据结构(C++版)[M]. 北京：清华大学出版社, 2011：83-85.
[2]牛客网. 串的模式匹配[DB/OL]. https://www.nowcoder.com/practice/084b6cb2ca934d7daad55355b4445f8a?tpId=49&&tqId=29363&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking