KMP算法,及其思想的应用
前言
最近在刷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
- next[0] 代表 t[0] ~ t[0],即 “A”,"A"的前缀和后缀都是空集,共有元素的长度为0。
- next[1] 代表 t[0] ~ t[1],即 “AB”,前缀为"A",后缀为"B",共有元素的长度为0。
- next[2] 代表 t[0] ~ t[2],即 “ABA”,前缀为"AB",后缀为"BA",共有元素的长度为1。
- next[3] 代表 t[0] ~ t[3],即 “ABAB”,前缀为"ABA",后缀为"BAB",共有元素的长度为2。
- next[4] 代表 t[0] ~ t[4],即 “ABABA”,前缀为"ABAB",后缀为"BBABA",共有元素的长度为3。
- 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算法是《算法第四版》里,关于字符串匹配的算法。
当时看到最后一章看不下去了,错过了这个算法,现在算是补上了。
唉,偷的懒迟早要补回来。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!