问题描述
输入：一个文本串S，和一个模式串P
输出：若干行，每行包含一个整数，表示s2在s1中出现的位置
在一个母字符串S（文本串）中查找一个子字符串P（模式串）有很多方法。Knuth-Morris-Pratt 字符串查找算法(简称“KMP”)是一种最常见的改进算法，由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
这个算法针对的是子串有对称属性，如果有对称属性，那么就需要向前查找是否有可以再次匹配的内容。
注意：这里的对称性，不是中心对称，而是中心字符块对称，比如不是abccba，而是abcabc这种对称。
KMP
一般最粗暴的方法，就是匹配失败后，一个字符一个字符往后挪来进行比较，比如：
KMP可以在匹配过程中失配的情况下，有效地多往后面跳几个字符，加快匹配速度。
下面先直接给出KMP的算法流程：
图一(a)
图一(b)
图二(a)
图二(b)
假设现在文本串S匹配到
i
位置，模式串P匹配到
j
位置
- 当前字符匹配成功（即
S[i] == P[j]
k++
j++
- 当前字符匹配失败（即
S[i] != P[j]
j = next[j]
j - next [j]
换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文详细阐述），即移动的实际位数为：
j - next[j]
，且此值≥1。
next数组（前缀数组）
每一个模式串P都有有一个固定的next数组，它记录着字符串匹配过程中失配情况下可以向前多跳几个字符，当然它描述的也是子串的对称程度，程度越高，值越大，当然之前可能出现再匹配的机会就更大。
这个next数组的求法是KMP算法的关键，看到别的地方到处是数学公式推导，我这里用图示的方法方便大家理解。
- 红色：模式串P当前已经匹配好的相同前后缀
- 蓝色：模式串P当前匹配的位置，就是
j
- 橙色：模式串P当前匹配的最长前缀的后一位，即为
k
如果
p[j] == p[k]
，则皆大欢喜，
next[j] = next[j - 1] + 1
p[j] != p[k]
，只能寻找更短的相同前后缀匹配，我们看下图
- 灰色：当前已经匹配好相同前后缀中的最长公共前后缀
- 紫色：当前已经匹配好相同前后缀中的前缀的后一位
因为红色部分是已经匹配好的，所以既然第二个的后面为灰色部分，第一个的前面和后面也为灰色部分，接下来对应的，第二个前面的也为灰色部分。
查阅
蓝色
与
紫色
是否匹配。
此时，又回到最初的那一步（递归），求解某个位置的next值是一个循环过程，不断检查 上一位的最长前缀的后一位.
如果相等
next[j] = next[k] + 1
，否则
k = next[k]
代码
//优化过后的next 数组求法
void GetNextval(char* p, int next[]) {
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1){
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k]){
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}
else{
k = next[k];
}
}
}