03. KMP 算法
03. KMP 算法
1. KMP 算法介绍
KMP 算法:全称叫做 「Knuth Morris Pratt 算法」,是由它的三位发明者 Donald Knuth、James H. Morris、 Vaughan Pratt 的名字来命名的。KMP 算法是他们三人在 1977 年联合发表的。
- KMP 算法思想:对于给定文本串
与模式串 ,当发现文本串 的某个字符与模式串 不匹配的时候,可以利用匹配失败后的信息,尽量减少模式串与文本串的匹配次数,避免文本串位置的回退,以达到快速匹配的目的。
1.1 朴素匹配算法的缺陷
在朴素匹配算法的匹配过程中,我们分别用指针
这样,在 Brute Force 算法中,如果从文本串
那么有没有哪种算法,可以让
1.2 KMP 算法的改进
如果我们可以通过每一次的失配而得到一些「信息」,并且这些「信息」可以帮助我们跳过那些不可能匹配成功的位置,那么我们就能大大减少模式串与文本串的匹配次数,从而达到快速匹配的目的。
每一次失配所告诉我们的信息是:主串的某一个子串等于模式串的某一个前缀。
这个信息的意思是:如果文本串
但是知道这个信息有什么用呢?
以刚才图中的例子来说,文本串的子串
- 文本串
从下标位置 开始连续的 个字符,一定与模式串 的前 个字符一模一样,即:"ABCAB" == "ABCAB"
。 - 而模式串的前
个字符中,前 位前缀和后 位后缀又是相同的,即"AB" == "AB"
。
所以根据上面的信息,我们可以推出:文本串子串的后
那么我们就可以将文本串中的
KMP 算法就是使用了这样的思路,对模式串
比如上述示例中模式串 "ABCAB" == "ABCAB"
。而根据「部分匹配表」中
1.3 next 数组
上文提到的「部分匹配表」,也叫做「前缀表」,在 KMP 算法中使用
简单而言,就是求:模式串
举个例子来说明一下,以 p = "ABCABCD"
为例。
,因为"A"
中无有相同前缀后缀,最大长度为 。 ,因为"AB"
中无相同前缀后缀,最大长度为 。 ,因为"ABC"
中无相同前缀后缀,最大长度为 。 ,因为"ABCA"
中有相同的前缀后缀"A"
,最大长度为 。 ,因为"ABCAB"
中有相同的前缀后缀"AB"
,最大长度为 。 ,因为"ABCABC"
中有相同的前缀后缀"ABC"
,最大长度为 。 ,因为"ABCABCD"
中无相同前缀后缀,最大长度为 。
同理也可以计算出 "ABCABDEF"
的前缀表为 "AABAAAB"
的前缀表为 "ABCDABD"
的前缀表为
在之前的例子中,当
但是这样移动的原理是什么?
其实在上文 「1.2 KMP 算法的改进」 中的例子中我们提到过了。现在我们将其延伸总结一下,其实这个过程就是利用了前缀表进行模式串移动的原理,具体推论如下。
如果文本串
- 文本串
从下标位置 开始连续的 个字符,一定与模式串 的前 个字符一模一样,即: 。 - 而如果模式串
的前 个字符中,前 位前缀和后 位后缀相同,即 ,并且要保证 要尽可能长。
可以推出:文本串子串的后
那么我们就可以将文本串中的
2. KMP 算法步骤
3.1 next 数组的构造
我们可以通过递推的方式构造
- 我们把模式串
拆分成 、 两部分。 表示前缀串开始所在的下标位置, 表示后缀串开始所在的下标位置,起始时 , 。 - 比较一下前缀串和后缀串是否相等。通过比较
和 来进行判断。 - 如果
,说明当前的前后缀不相同。则让后缀开始位置 不动,前缀串开始位置 不断回退到 位置,直到 为止。 - 如果
,说明当前的前后缀相同,则可以先让 ,此时 既是前缀下一次进行比较的下标位置,又是当前最长前后缀的长度。 - 记录下标
之前的模式串 中,最长相等前后缀的长度为 ,即 。
3.2 KMP 算法整体步骤
- 根据
数组的构造步骤生成「前缀表」 。 - 使用两个指针
、 ,其中 指向文本串中当前匹配的位置, 指向模式串中当前匹配的位置。初始时, , 。 - 循环判断模式串前缀是否匹配成功,如果模式串前缀匹配不成功,将模式串进行回退,即
,直到 时或前缀匹配成功时停止回退。 - 如果当前模式串前缀匹配成功,则令模式串向右移动
位,即 。 - 如果当前模式串 完全 匹配成功,则返回模式串
在文本串 中的开始位置,即 。 - 如果还未完全匹配成功,则令文本串向右移动
位,即 ,然后继续匹配。 - 如果直到文本串遍历完也未完全匹配成功,则说明匹配失败,返回
。
3. KMP 算法代码实现
# 生成 next 数组
# next[j] 表示下标 j 之前的模式串 p 中,最长相等前后缀的长度
def generateNext(p: str):
m = len(p)
next = [0 for _ in range(m)] # 初始化数组元素全部为 0
left = 0 # left 表示前缀串开始所在的下标位置
for right in range(1, m): # right 表示后缀串开始所在的下标位置
while left > 0 and p[left] != p[right]: # 匹配不成功, left 进行回退, left == 0 时停止回退
left = next[left - 1] # left 进行回退操作
if p[left] == p[right]: # 匹配成功,找到相同的前后缀,先让 left += 1,此时 left 为前缀长度
left += 1
next[right] = left # 记录前缀长度,更新 next[right], 结束本次循环, right += 1
return next
# KMP 匹配算法,T 为文本串,p 为模式串
def kmp(T: str, p: str) -> int:
n, m = len(T), len(p)
next = generateNext(p) # 生成 next 数组
j = 0 # j 为模式串中当前匹配的位置
for i in range(n): # i 为文本串中当前匹配的位置
while j > 0 and T[i] != p[j]: # 如果模式串前缀匹配不成功, 将模式串进行回退, j == 0 时停止回退
j = next[j - 1]
if T[i] == p[j]: # 当前模式串前缀匹配成功,令 j += 1,继续匹配
j += 1
if j == m: # 当前模式串完全匹配成功,返回匹配开始位置
return i - j + 1
return -1 # 匹配失败,返回 -1
print(kmp("abbcfdddbddcaddebc", "ABCABCD"))
print(kmp("abbcfdddbddcaddebc", "bcf"))
print(kmp("aaaaa", "bba"))
print(kmp("mississippi", "issi"))
print(kmp("ababbbbaaabbbaaa", "bbbb"))
4. KMP 算法分析
- KMP 算法在构造前缀表阶段的时间复杂度为
,其中 是模式串 的长度。 - KMP 算法在匹配阶段,是根据前缀表不断调整匹配的位置,文本串的下标
并没有进行回退,可以看出匹配阶段的时间复杂度是 ,其中 是文本串 的长度。 - 所以 KMP 整个算法的时间复杂度是
,相对于朴素匹配算法的 的时间复杂度,KMP 算法的效率有了很大的提升。
参考资料
- 【书籍】柔性字符串匹配 - 中科院计算所网络信息安全研究组 译
- 【书籍】ACM-ICPC 程序设计系列 - 算法设计与实现 - 陈宇 吴昊 主编
- 【博文】从头到尾彻底理解 KMP - 结构之法 算法之道 - CSDN博客
- 【博文】字符串匹配的 KMP 算法 - 阮一峰的网络日志
- 【题解】多图预警 - 详解 KMP 算法 - 实现 strStr() - 力扣
- 【题解】「代码随想录」KMP算法详解 - 实现 strStr() - 力扣
来源:https://github.com/itcharge/LeetCode-Py