前言

最近在刷leetcode，在写关于字符串方面的题目。

在一个字符串匹配的题目中，我使用了暴力匹配的算法，可想而知，复杂度起步就是 O(mn) （m和n分别是要被匹配的字符串和匹配样式字符串的长度）。

在看大佬们的题解时，发现有人使用了一个叫 KMP 算法的东西。

好家伙，我还真不知道这是个啥。当时看解析，KMP属实太抽象了，搞不明白啥意思。

看了半天，把思想搞明白了，看了一眼代码，我还是好家伙，这又是啥玩意。

然后就果断躺平，想着哪天再把 KMP 复习一下。

弄着弄着就忘记再去复习复习了。直到今天做另外一道题，214. 最短回文串，看到题解里，有人用了 KMP 思想，巧妙地解决了这道题让我想起来，KMP 还得好好在学习一下。

KMP是什么

Knuth-Morris-Pratt 字符串查找算法，简称为 KMP算法，常用于在一个文本串 S 内查找一个模式串 P 的出现位置。

KMP算法是用来做什么的？

要了解KMP算法，首先需要了解，这个算法是用来做什么的，应用场景是什么。

那我们从最简单的字符串匹配开始。

从上面的GIF图中可以看到，在每一次匹配时，逐个匹配字符。

当出现字符不匹配时，将 s 与 t 的指针都清零了，并且 t 只往后前进一个字符。

假如 s 的长度为m，t 的长度为n，那么这种暴力匹配的时间复杂度为 O((m-n)*n)。

目前 s 和 t 的长度还比较短，如果长度再增长，消耗的时间马上就上去了。

那么，有没有算法能够帮助我们减少这种字符串匹配的时间嗯？

分析

我们来分析一下，有没有什么方法，能够减少比较的次数。

在索引为1的地方，我们来分析一下。

此时我们前面4个字符都已经匹配了，但是在最后一个字符进行比较时，匹配失败。

按照暴力法，下一步就是将 t 字符串向后移动，并且指针清零。

但是这一步几乎就是浪费时间，因为 t 字符串本身是 ABABC，如果前4个字符匹配了，那么向后移动一位完全不可能匹配上。

我们实际上可以直接跳到第二个 A 处。

有没有什么方法，可以让我们从 t 匹配串中提取出信息呢？让我们在匹配失败的时候，可以不用从头开始回溯。

KMP算法

KMP算法的核心就在于，对于 t 匹配串进行了处理，从其中获取了信息，并将其保存，一般称这个数组叫做 next 数组。

next数组

next数组的值是代表着字符串的前缀与后缀相同的最大长度,(不能包括自身)。

"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；

"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

举个例子：

模式串t： A B A B A A

下标: 0 1 2 3 4 5

next: 0 0 1 2 3 1

1. next[0] 代表 t[0] ~ t[0]，即 “A”，"A"的前缀和后缀都是空集，共有元素的长度为0。
2. next[1] 代表 t[0] ~ t[1]，即 “AB”，前缀为"A"，后缀为"B"，共有元素的长度为0。
3. next[2] 代表 t[0] ~ t[2]，即 “ABA”，前缀为"AB"，后缀为"BA"，共有元素的长度为1。
4. next[3] 代表 t[0] ~ t[3]，即 “ABAB”，前缀为"ABA"，后缀为"BAB"，共有元素的长度为2。
5. next[4] 代表 t[0] ~ t[4]，即 “ABABA”，前缀为"ABAB"，后缀为"BBABA"，共有元素的长度为3。
6. next[5] 代表 t[0] ~ t[5]，即 “ABABAA”，前缀为"ABABAA"，后缀为"BABAA"，共有元素的长度为1。

由此，我们计算出了next

用next数组来解决上面的例子

我们已经计算出了上面例子中的next数组。

从GIF图可以看到，我们通过next数组，使用 j = next[j-1]，来快速计算恢复的下表，直接将下表从4恢复为2，不用从0开始恢复，从而达到跳跃式匹配。

个人的理解

上面的解释相对来说，比较枯燥且难以理解，下面是我自己思考和理解这个算法的过程，也希望我思考的方式可以给读者一定的启发。

在最开始学习这一块的时候，我特别不能理解，next数组到底是个什么玩意，为什么用上面那种方法计算了next数组，在出现匹配失败时，为什么按照next数组来计算，就能快速回退呢？

---

虽然上面对于计算next数组的方法，已经写的比较详细了。

但是一开始学习时，我仍然不明白这么做是为了干什么。尤其是计算前缀与后缀相同的长度，让我一直有点懵。

但是我们仔细对照着next数组与原字符串对比。

对于索引为0和1的字符，即 A 和 B，其next数组的值为0。

而对于索引为2的字符，即第二个A，我们可以看到，其next数组的值为1。当索引为3的字符，即第二个B匹配失败时，说明前面 “ABA” 前缀字符串匹配是对的，但是加上当前的 “B”，字符串 “ABAB” 匹配失败。

但是next数组保存了之前 t 字符串的信息，所以我们把前缀变成 “A” ，然后继续匹配，看能不能匹配的上。

---

好，那我们在看索引为3的字符，即第二个B。

其next数组对应的值为2。当我们匹配索引为4的字符，即“C”时，如果匹配失败，表明前缀 “ABAB” 匹配是没问题的，但是加上了 “C”，“ABABC” 匹配不上。

前面说了，索引为3的 “B” 对应next数组的值为2，那么我们的前缀可以变成 “AB” ，也就是从1开始，到2的字字符串，这样我们再去看能不能匹配的上。

KMP思想应用

其实这道leetcode的题并不完全是KMP的题，其只不过借助了KMP算法中next数组的思想。

题目

214. 最短回文串 这道题是hard，题目是这样的

题目的主要意思是，从字符串的开头开始找，找到最长的回文串，然后在字符串的开头加上回文串后面的字母，让整个字符串变成回文串。

比如示例1: “aacecaaa”，其中字符串的前七位组成的 “aacecaa” 是回文串，然后就在字符串的开头加上后面剩下的 “a”， 就组成了 “aaacecaaa”

比如示例2: “abcd”，从开头找，只有 “a” 算是回文串，所以将 “bcd” 反转后，加在最前面，变成了 “dcbabcd”，成为了回文串。

所以本题目最大的难点就是从字符串的开头开始，最长的回文串。

说到回文串，最先想到的就是中心拓展法，也就是本题的暴力解法。

由于时间复杂度比较高，并且做法和正常的回文串方法一样，所以就不在本文赘述。

分析

既然是找到最长的，从字符串开头开始找的回文串，那么根据回文串的性质，我们知道该字符串反转之后，从字符串开头开始的回文串，就会变成从字符串末尾开始的回文串。

比如 “abacd”，反转后变为 “dcaba”，前缀回文是"aba"，所以反转后的后缀回文也是"aba"。

前缀。。。后缀。。。这不就是KMP计算next的方法吗？

是的，这道题最巧妙的方法就是用KMP计算next数组的方法。

我们将字符串和其自身反转后的字符串合并在一起，然后计算next数组。

比如 “abacd”，我们将其和反转后的 “dcaba” 合并，变为 “abacddcaba”。

然后通过计算next数组后，直接看next数组最后一个元素，其就代表了前缀回文串的长度。

但是

但是，我们用这种合并方式，会出现一种问题。

比如 “aaa”，如果我们直接合并，最后的到的字符串就是 “aaaaaa”，这显然又问题啊。

那么我们可以通过在中间添加一个无关的字符，来作为间隔。

这里我用了 # 作为间隔。

代码

总结

说起来，KMP算法是《算法第四版》里，关于字符串匹配的算法。

当时看到最后一章看不下去了，错过了这个算法，现在算是补上了。

唉，偷的懒迟早要补回来。