KMP Algorithm
我们先从模式匹配算法开始说起。
模式匹配
所谓模式匹配，就是子串的定位操作。
求子串位置的定位函数
Index(S,T,pos)，其中T为模式串。
简单的模式匹配算法最坏时间复杂度为O(nm)，其中n和m分别为主串和模式串的长度。下面介绍改进的模式匹配算法(KMP算法)，此算法将时间复杂度降低至O(m+n).
在一般情况下，普通模式匹配的实际执行时间近似为O(m+n)，因此至今仍被采用。 KMP算法仅在主串与子串有很多“部分匹配”时才显得比普通算法快得多，其主要优点是主串不回溯。
KMP算法
KMP算法的核心是next数组。
几个基本概念
字符串的前缀：除最后一个字符以外，字符串的所有头部子串；
字符串的后缀：除第一个字符外，字符串的所有尾部子串；
部分匹配值(PM)：字符串的前缀和后缀的最大相等前后缀长度。
下面是一个PM的表：
| number | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| S | a | b | c | a | c |
| PM | 0 | 0 | 0 | 1 | 0 |
公式
移动位数 = 已匹配的字符数 - 对应的部分匹配值
上面的公式不是很方便，与时我们将字符串"abcac"的PM表右移一位，得到如下next数组：
| Number | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| S | a | b | c | a | c |
| PM | -1 | 0 | 0 | 0 | 1 |
- 第一个元素右移以后空缺的用-1来填充，因为若是第一个元素匹配失败，则需要将子串向右移动一位，而不需要计算子串移动的位数。
- 最后一个元素在右移的过程中溢出，因为原来的子串中，最后一个元素的PM是其下一个元素使用的，但是显然已经没有下一个元素，所以可以舍去。
有时候为了使公式更加简洁、计算简单，将next数组整体+1。因此，上面的next数组也可写为：
| Number | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| S | a | b | c | a | c |
| PM | 0 | 1 | 1 | 1 | 2 |
next[j]的含义
在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较。
next数组的内在关系
下面举一个例子来说明。
已知next数组的部分关系，推测未知位置的数值。
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 模式 | a | b | a | a | b | c | a | b | a |
| next[j] | 0 | 1 | 1 | 2 | 2 | 3 | ? | ? | ? |
计算next[7]：因为next[6] = 3，c = p6 != p3 = a；因为next[next[6]] = next[3] = 1，c = p6 != p1 = a，于是next[7] = next[1] + 1 = 0 + 1 = 1；
计算next[8]：因为next[7] = 1，p7 = p1 = a，于是next[8] = next[7] + 1 = 1 + 1 = 2；
计算next[9]：因为next[8] = 2, p8 = p2 = b，于是next[9] = next[8] + 1 = 2 + 1 = 3;
【注意】next数组以及子串的下标是从1开始。
KMP的进一步优化
【修正next数组】如果出现p(j) = p(next[j])，那么就将next[j]修正为next[next[j]]，直至两者不相等为止，更新后的数组命名为nextval。下面是例子：
| 主串 | a | a | a | b | a | a | a | a | b |
|---|---|---|---|---|---|---|---|---|---|
| 模式 | a | a | a | a | b | ||||
| j | 1 | 2 | 3 | 4 | 5 | ||||
| next[j] | 0 | 1 | 2 | 3 | 4 | ||||
| nextval[j] | 0 | 0 | 0 | 0 | 4 |
原因：单用next数组会出现很多毫无意义的失配。所以要对next数组进行修正。修正后的next数组为nextval数组，但是匹配算法不变。
附录
求next值的程序
void get_next(string T, int next[]) {
int i = 1, j = 0;
next[1] = 0;
while (i < T.length) {
if (!j || T.ch[i] == T.ch[j]) {
++i; ++j;
next[i] = j; // 若pi=pj，则next[j+1] = next[j] + 1
}
else j = next[j]; // 否则令j = next[j]，循环继续
}
}
求nextval值的程序
void get_nextval(string T, int nextval[]) {
int i = 1, j = 0;
nextval[1] = 0;
while (i < T.length) {
if(!j || T.ch[i] == T.ch[j]) {
++i; ++j;
if(T.ch[i] != T.ch[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
}