KMP算法用于子字符串查找（匹配）。
KMP是三个科学家[Knuth-Morris-Pratt]发明的，旨在对暴力匹配算法的改进，时间复杂度从 O(m*n) 减到 O(m+n)
- KMP算法的重点难点在于理解 PMT(Partial Match Table) “部分匹配表”，这个表决定每次遇到不匹配时， 新的子字符串的查找位置。
- 比如从字符串S1=> "BBC ABCDAB ABCD ABCDABDE" 中查找 S2=> "ABCDABD"，暴力破解的算法思路是：
- 拿S1的第一位，和S2的第一位对比
- 不相等则移位到S1的下一位，S2则从头开始匹配，即拿S1的第二位，对比S2的第一位，直到匹配到为止
- 相等则两个字符串数组指针均后移一位
- 直到子字符串指针移到末尾，或者要查找的字符串指针移到末尾
KMP算法主要解决第二步，即不匹配发生时，力求S1的指针位置不发生变化，S2指针位置移动最少。
这么做的依据是，在前一次的比较过程中，其实我们已经知道了一些信息，因此避免多余的比较。比如比较到了S1的第四位，子字符串的前六位"ABCDAB"都可以匹配，但是第七位"D"无法和S1的" "匹配，
- 如果按照暴力的思路，这时应该S1的指针回到第五位，S2的指针归零。但是我们知道，S2[0] != S2[1]，而S2[1] = S1[5]，所以，S2[0] != S1[5]，这一步在之前的比较重，就已经确定了，所以完全可以避免
- 同理，因为S2[0] != S2[2]， 但是S2[2] = S1[6]，所以S2[0] != S1[6]，所以也可以避免重复比较。
- 问题的关键就在于，如果我们不动S1的指针（目前指向S1[10]），那么S2的指针应该移动到第几位。
先说结论，应该移动到 当前子字符串指针所在位置的 “部分匹配值”的位置
部分匹配值
那么什么是部分匹配值呢，为什么要移动这个位置是对的呢
某个位置的部分匹配值，就是从开头到当前位置，这一段字符的相同前缀与后缀的最大长度。
比如 abcabc 的前缀有 {a, ab, abc, abca, abcab}， 后缀有 {c, bc, abc, cabc, bcabc}， 唯一相同的只有abc，所以这个字符串在第六位的部分匹配值是3；而他的第五位的部分匹配值，就是计算abcab的部分匹配值，即从{a, ab, abc, abca} 与 {b, ab, cab, bcab}中选出相同的前后缀的最大长度，即2；
所以，"ABCDABD"的部分匹配值表为
| 字符 | A | B | C | D | A | B | D |
|---|---|---|---|---|---|---|---|
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 部分匹配值 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
为什么部分匹配值是正确的
使用S1=> "BBC ABCDAB ABCD ABCDABDE" 中查找 S2=> "ABCDABD"来说明：
图一
这时：
i = 10
j = 6
查表知，next[j] = 2
image.png
- 图一的【j】前的子字符串的部分匹配值为2，说明，子字符串的前两位和最后两位是相同的
- 【i】位置前的6位和 【j】前的6位相同
- 要搜索的字符串位置【i】的前两位，和子字符串的最前两位相同，所以可以跳过
- 所以直接比较位置【i】和新的位置【j】
所以部分匹配值是正确的
附上PHP版代码：
function getKmpNext($string) {
$strlen = strlen($string);
$i = 0;
$j = - 1;
$next[0] = -1;
while ($i < $strlen)
{
if ($j == -1 || $string[$i] == $string[$j])
{
++$i;
++$j;
$next[$i] = $j;
}
else
$j = $next[$j];
}
return $next;
}
function kmp($string, $substr)
{
$i = 0; $j = 0;
$strlen = strlen($string);
$sublen = strlen($substr);
$next = getKmpNext($substr);
while($i < $strlen && $j < $sublen) {
if($j == -1 || $string[$i] === $substr[$j]) {
$i ++;
$j ++;
}
else {
$j = $next[$j];
}
}
if($j == $sublen) {
return $i - $j;
}
return "Not found";
}
