Shio Y. Blog

KMP 算法是用于解决字符串匹配问题的高效算法。

字符串匹配问题

对于两个字符串 T ( 主串 ) 、P ( 模式串 ) ，T 是否包含 P，如果是，那么它在 T 的什么位置。一个典型的应用场景就是一段代码中搜索目标关键字如 function，文本编辑器需要找到它们的位置并高亮。

朴素解法

从 T 的每个字符开始，与 P 进行字符的逐一匹配检测。可以想象 T 是一段铺在铁轨上的标识，P 是铁轨上的一段列车。列车每移动一格，就查看列车的每个车厢是否与铁轨上的标识相一致。

KMP 算法

每次匹配失败后，P 只能位移一格显得有些效率低下了。有没有什么办法让它排除掉显然不可能的情况，从而一次多移动几格呢。

要实现这一目的，我们只能从已有的信息中获取线索。假设上一次匹配过程中能够匹配上的最大字串为 abcab:

可以看到 P 移动 1 或者 2 个位置显然是不可能的，因为

• abca != bcab
• abc != bca

而 P 移动 3 步尚有一试的可能，因为 ab == ab。

我们发现上述不等式中，左侧是 P 的前 k 个字符 ( 前缀 ) ，右侧是 P 的后 k 个字符 ( 后缀 ) 。因此我们只需要找到最大的一个 k，使得左侧和右侧相等，从而使 P 可以移动多步，来进行下一次匹配。如上述实例中，abcab 最大 k=2 ( 前缀'ab'=后缀'ab' ) ，P 可以向前移动 3 步。

在实际匹配中，临时计算已匹配字符串的最大 k 显然不够效率。我们知道已匹配的字符串永远是 P 的前缀子串，因此可以预制好一个 next 数组，用于存储每个子串所对应的最大 k。

具体定义：next[i]：对于模式串 P 中[0, i]区间内的子串，使其 k 个字符前缀与 k 个字符后缀相等的最大 k 的值

如何预制 Next 数组

我们当然可以从长度 1 开始，从两边开始遍历判断前缀和后缀是否相等，当然这样的复杂度就来到了 O(m^2) (m=p.length) ，并不高效。

仔细观察可以发现这竟然是一个动态规划问题，可以得出一个递推公式。

例如模式串 P 如下，假设我们已知 next[0]到 next[x-1]的值，要求 next[x]。

通过 next[x-1]可知长度为 now 的子串 A ( T[0:5] ) 和 B ( T[9:13] ) 相等。因此只要判断 p[now+1]与 p[x]是否相等即可

• 如果相等，则 next[x]=next[x-1] + 1。
• 如果不相等，则 next[x]一定小于 now+1 了。下一个可能的情况是在 P[0..x-1]中找到一个 now2 长度的前缀和后缀，使其相等。接下来判断 P[now2]==P[x]。如果相同，则可以求出 next[x]=now2+1。如果不相同，则需要继续缩短 now2 的长度。

在此过程中，可以注意到 P[0..x]的一个 now2 长度的前缀和后缀一定出现在子串 A 和 B 中，而 A 和 B 是相等的。我们惊奇的发现这不就是一个相同问题的子问题吗，now2 的值不就存储在 next 数组中吗？即 now2 = next[now-1]。

代码

因为 next 数组中新的元素总是由数组中已求的的元素得出的，所以可以使用动态规划的方法得到整个数组

我们得到了 next 数组后，接下来的操作就和朴素算法类似

Refer

• 如何更好地理解和掌握 KMP 算法?