KMP 算法

KMP算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。

它的核心就是 PMT，也就是 next 表。

暴力的匹配算法就是把子串和主串逐位进行匹配，如果不匹配，则子串右移一位。这种情况下必定会产生很多无效匹配，复杂度为 O(mn)。

KMP 说难不难，说简单也不简单，先要理解 PMT。

先解释一下字符串的“前缀”和“后缀”。

• 如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。
• 同样可以定义后缀A=SB， 其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。

对于一个字符串，它的 PMT 值就是前缀集合和后缀集合中相同最长的字符串的长度。

• 对于字符串 ab，前缀集合 {“a”}，后缀集合 {“b”}，可见部分匹配表的值为0
• 对于字符串 aba，前缀集合{“a”,”ab”}，后缀集合 {“ba”, “a”}，可见部分匹配表为1
• 对于字符串 abab，前缀集合{“a”,”ab”,”aba”}，后缀集合{“bab”,”ab”,”b”}，最长的相同字符串为 “ab”，所以是2
• 对于字符串 ababa，前缀集合{“a”,”ab”,”aba”,”abab”}，后缀集合{“baba”,”aba”,”ba”,”a”}，最长的相同字符串为 “aba”，所以为 3

那么 PMT 表的这个特性有什么好处？好处就是字符匹配过程中，主串上的指针永不后退。

我们一般假定两个指针，一个指针在主串上移动，一个指针在匹配串上移动（如果匹配失败，这个指针回退到指定地方）。

如果在 j 处字符不匹配，那么由于前边所说的模式字符串 PMT 的性质，主字符串中 i 指针之前的 PMT[j −1] 位就一定与模式字符串的第 0 位至第 PMT[j−1] 位是相同的。这是因为主字符串在 i 位失配，也就意味着主字符串从 i−j 到 i 这一段是与模式字符串的 0 到 j 这一段是完全相同的。

这个算法难度大，主要在于难以在脑中可视化，不像是排序算法，树算法，可以直接想象出来。更多的可视化内容可以参考：

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