字符串匹配算法 - KMP算法
- 1 min数据结构与算法系列（二十七）
KMP 算法可以说是字符串匹配算法中最知名的算法了，KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。
KMP 算法的核心思想
假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况，从而避免 BF 算法这种暴力匹配，提高算法性能。下面我们来探讨下这个规律如何找到。
参考下面个主串和模式串的匹配，当模式串移动到当前位置，比对到最后一个字符 D 时，发现与主串不匹配，如果按照 BF 算法，就是把模式串往后移一位，再逐个比较，这样做固然可以，但是效率很差：
一个基本事实是，当 D 与主串不匹配时，我们已知前面的主串序列是「ABCDA」，如果把模式串往后移一位肯定和主串不匹配，我们可不可以直接把模式串移到下一个可能和 A 匹配的主串位置？
实际上，KMP 算法正是基于这一理念，设法利用这个已知信息，不把模式串移到已经比较过的位置，继续把它向后移，这样综合下来就极大提高了搜索匹配效率。
怎么找到这个规律，确定把模式串往后移多少位呢？在模式串和主串匹配的过程中，我们把不能匹配的那个字符仍然叫作「坏字符」，把已经匹配的那段字符串叫作「好前缀」：
在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的下标位置，然后将模式串后移到该位置即可。
这里，我们要解释几个概念：
- 后缀子串：以某个字符串最后一个字符为尾字符的子串（不包含字符串自身），比如上面的 ababa，后缀子串为 baba、aba、ba、a；
- 前缀子串：以某个字符串第一个字符为首字符的子串（不包含字符串自身），还是以 ababa 为例，前缀子串为 a、aba、abab；
- 最长可匹配后缀子串：后缀子串与前缀子串最长可匹配子串，也可叫做共有子串，以 ababa 为例，自然是 aba 了，长度为3；
- 最长可匹配前缀子串：与上面定义相对，即前缀子串与后缀子串最长可匹配子串。最长可匹配前缀子串和最长可匹配后缀子串肯定是一样的。
假设坏字符所在位置是 j，最长可匹配后缀子串长度为 k，则模式串需要后移的位数为 j-k。每当我们遇到坏字符，就将模式串后移 j- k 位，直到模式串与对应主串字符完全匹配；如果移到最后还是不匹配，则返回 -1。这就是 KMP 算法的核心思想。
KMP 算法的实现
了解了核心思想，接下来，就可以考虑如何实现 KMP 算法了，实现 KMP 算法最核心的部分是构建一个用来存储模式串中每个前缀子串（这些前缀都有可能是好前缀）最长可匹配前缀子串的结尾字符下标数组，我们把这个数组叫做 next 数组，对于上面 ababacd 这个模式串而言，对应的 next 数组如下：
其中，数组的下标是前缀子串结尾字符下标，数组的值是这个前缀的最长可匹配前缀子串的结尾字符下标。
有了这个 next 数组，我们就可以实现 KMP 匹配算法的核心代码了：
// KMP 算法 PHP 实现代码，$a 表示主串，$n 表示主串长度，$b 表示模式串，$m 表示模式串长度
function kmp($a, $n, $b, $m)
{
$next = generateNexts($b, $m); // 生成 next 数组
$j = 0;
for ($i = 0; $i < $n; $i++) { // 遍历主串
while ($j > 0 && $a[$i] != $b[$j]) {
// 如果主串字符和模式串字符不相等，
// 更新模式串坏字符下标位置为好前缀最长可匹配前缀子串尾字符下标+1
// 然后从这个位置重新开始与主串匹配
// 相当于前面提到的把模式串向后移动 j - k 位
$j = $next[$j - 1] + 1;
}
if ($a[$i] == $b[$j]) {
$j++;
}
if ($j == $m) {
return $n - $m + 1; // 全部相等，找到匹配位置
}
}
return -1;
}
接下来就是如何生成 next 数组了，这一步是最难的，我们现在可以参考上面 next 数组生成原理通过循环比对前缀子串和后缀子串的方式去理解，毕竟我们在实际开发中不太可能自己去实现 KMP 算法，了解原理即可，以后讲到动态规划，会用动态规划来实现它。这里就不再深入探究了。