KMP算法

KMP算法用于子字符串查找（匹配）。

KMP是三个科学家[Knuth-Morris-Pratt]发明的，旨在对暴力匹配算法的改进，时间复杂度从 O(m*n) 减到 O(m+n)

• KMP算法的重点难点在于理解 PMT(Partial Match Table) “部分匹配表”，这个表决定每次遇到不匹配时， 新的子字符串的查找位置。
• 比如从字符串S1=> "BBC ABCDAB ABCD ABCDABDE" 中查找 S2=> "ABCDABD"，暴力破解的算法思路是：
  1. 拿S1的第一位，和S2的第一位对比
  2. 不相等则移位到S1的下一位，S2则从头开始匹配，即拿S1的第二位，对比S2的第一位，直到匹配到为止
  3. 相等则两个字符串数组指针均后移一位
  4. 直到子字符串指针移到末尾，或者要查找的字符串指针移到末尾

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

所以，j应该移动到2的位置，即： image.png

1. 图一的【j】前的子字符串的部分匹配值为2，说明，子字符串的前两位和最后两位是相同的
2. 【i】位置前的6位和 【j】前的6位相同
3. 要搜索的字符串位置【i】的前两位，和子字符串的最前两位相同，所以可以跳过
4. 所以直接比较位置【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";
}