引言
大家在编程的时候，经常会碰到要在一个长字符串里找一个短字符串的情况。比如说，在一篇文章里找某个关键词，或者在代码文件里找特定的代码片段。一般的做法是一个字符一个字符地去比对，不过这种方法在字符串很长的时候就会变得很慢。今天咱们就来聊聊一种能解决这个问题的厉害算法——KMP算法。它能在线性时间内完成字符串匹配，效率特别高，而这其中的关键就是它的部分匹配表。接下来咱们就一步步揭开这个算法的神秘面纱。
一、传统字符串匹配方法的问题
先说说传统的字符串匹配方法。假如我们有一个长字符串 text 和一个短字符串 pattern，想要看看 pattern 是不是在 text 里面，一般会这么做：
# Python 示例
def naive_search(text, pattern):
n = len(text)
m = len(pattern)
for i in range(n - m + 1):
j = 0
# 逐字符匹配
while j < m:
if text[i + j] != pattern[j]:
break
j += 1
if j == m:
print(f"Pattern found at index {i}")
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
naive_search(text, pattern)
这种方法就是从 text 的第一个字符开始，和 pattern 的第一个字符比对。要是一样，就接着比对下一个字符；要是不一样，就把 text 的比对位置往后移一位，再重新开始和 pattern 比对。
这种做法虽然简单，但是效率不高。想象一下，如果 text 特别长，比如说有几百万个字符，而 pattern 也有上千个字符。那每次只要有一个字符不匹配，就得从头开始比对，这样会浪费很多时间。而且，在最坏的情况下，时间复杂度会达到 $O(n*m)$，这里 $n$ 是 text 的长度，$m$ 是 pattern 的长度。当 $n$ 和 $m$ 都很大的时候，这个算法就会变得特别慢。
二、KMP算法的基本思想
KMP算法的全称是克努斯 - 莫里斯 - 普拉特字符串查找算法，它的核心思想是利用已经匹配过的信息，避免在匹配过程中做不必要的回溯。也就是说，当我们在 text 和 pattern 比对的时候，如果某个位置不匹配了，我们不用像传统方法那样把 text 的比对位置只往后移一位，而是根据已经匹配的部分，把 pattern 往后移动一定的距离，然后继续比对。
那怎么知道该移动多少距离呢？这就用到了部分匹配表（Partial Match Table，简称 PMT）。这个表记录了 pattern 中每个位置之前的子串的最长公共前后缀的长度。什么是最长公共前后缀呢？比如说，对于字符串 "ABAB"，它的前缀有 "A"、"AB"、"ABA"，后缀有 "B"、"AB"、"BAB"，最长的公共前后缀就是 "AB"，长度是 2。
三、部分匹配表的构建原理
构建部分匹配表是 KMP 算法的关键。我们要为 pattern 中的每个位置 i 计算出以 pattern[0] 到 pattern[i] 这个子串的最长公共前后缀的长度。
下面是构建部分匹配表的 Python 代码：
# Python 示例
def compute_lps(pattern):
m = len(pattern)
lps = [0] * m # 初始化部分匹配表
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
pattern = "ABABCABAB"
lps = compute_lps(pattern)
print("Partial Match Table (LPS):", lps)
代码解释
- 初始化部分匹配表：我们先创建一个和
pattern长度一样的数组lps，用来存储每个位置的最长公共前后缀长度，初始值都设为 0。 - 扫描
pattern：用两个指针i和length。i用来遍历pattern，length用来记录当前的最长公共前后缀长度。 - 匹配字符：如果
pattern[i]和pattern[length]相等，说明找到了一个更长的公共前后缀，length加 1，把length的值赋给lps[i]，然后i也加 1。 - 不匹配字符：如果不相等，就看
length是不是 0。如果length不是 0，就把length更新为lps[length - 1]，也就是利用之前计算好的信息，继续尝试匹配。如果length是 0，说明没有公共前后缀，把lps[i]设为 0，i加 1。
示例说明
还是以 pattern = "ABABCABAB" 为例，我们来一步步看看部分匹配表是怎么构建的：
- 当
i = 0时，子串只有一个字符"A"，没有公共前后缀，所以lps[0] = 0。 - 当
i = 1时，子串是"AB"，没有公共前后缀，lps[1] = 0。 - 当
i = 2时，子串是"ABA"，最长公共前后缀是"A"，长度为 1，所以lps[2] = 1。 - 当
i = 3时，子串是"ABAB"，最长公共前后缀是"AB"，长度为 2，所以lps[3] = 2。 - 当
i = 4时，子串是"ABABC"，没有公共前后缀，lps[4] = 0。 - 以此类推，最终得到的部分匹配表
lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]。
四、利用部分匹配表实现线性时间复杂度的字符串匹配
有了部分匹配表，我们就可以用 KMP 算法来进行字符串匹配了。下面是完整的 KMP 算法的 Python 代码：
# Python 示例
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
lps = compute_lps(pattern)
i = 0 # 指针用于遍历 text
j = 0 # 指针用于遍历 pattern
while i < n:
if pattern[j] == text[i]:
i += 1
j += 1
if j == m:
print(f"Pattern found at index {i - j}")
j = lps[j - 1]
elif i < n and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)
代码解释
- 初始化指针：用
i来遍历text，j来遍历pattern。 - 匹配字符：如果
pattern[j]和text[i]相等，i和j都加 1。 - 匹配成功：如果
j等于pattern的长度，说明找到了一个匹配的位置，输出位置信息，然后把j更新为lps[j - 1]，继续寻找下一个匹配。 - 不匹配字符：如果不相等，看
j是不是 0。如果j不是 0，把j更新为lps[j - 1]，利用部分匹配表的信息，避免不必要的回溯。如果j是 0，说明pattern的第一个字符就不匹配，把i加 1。
复杂度分析
KMP 算法的时间复杂度是 $O(n + m)$，这里 $n$ 是 text 的长度，$m$ 是 pattern 的长度。因为构建部分匹配表的时间复杂度是 $O(m)$，而字符串匹配的过程时间复杂度是 $O(n)$，两者加起来就是 $O(n + m)$。这比传统的字符串匹配算法的 $O(n*m)$ 要快很多。
五、应用场景
文本编辑器
在文本编辑器里，我们经常会用到查找功能，比如在一篇文档里找某个关键词。KMP 算法可以快速地在大段文本中找到匹配的位置，提高查找效率。
生物信息学
在生物信息学中，经常需要在 DNA 序列里查找特定的基因片段。DNA 序列通常很长，KMP 算法的线性时间复杂度可以大大减少查找时间。
网络爬虫
网络爬虫在抓取网页内容时，可能需要在大量的 HTML 代码中查找特定的标签或关键词。KMP 算法可以帮助快速定位这些内容。
六、技术优缺点
优点
- 高效：KMP 算法的时间复杂度是线性的，在处理长字符串时，比传统的字符串匹配算法快很多。
- 避免回溯：利用部分匹配表，避免了在匹配过程中不必要的回溯，提高了效率。
缺点
- 空间开销：需要额外的空间来存储部分匹配表，对于非常长的
pattern，会占用一定的内存。 - 实现复杂：相比传统的字符串匹配算法，KMP 算法的实现要复杂一些，理解和调试起来可能有一定难度。
七、注意事项
- 部分匹配表的计算：部分匹配表的计算是 KMP 算法的关键，要确保计算正确。在实际应用中，可以先对部分匹配表的计算进行测试，保证其准确性。
- 边界情况：在编写代码时，要注意处理边界情况，比如
text或pattern为空的情况，避免出现错误。
八、文章总结
KMP 算法是一种非常高效的字符串匹配算法，它通过构建部分匹配表，利用已经匹配的信息，避免了不必要的回溯，实现了线性时间复杂度的字符串匹配。虽然它的实现相对复杂，并且需要额外的空间来存储部分匹配表，但在处理长字符串时，它的效率优势非常明显。在实际应用中，我们可以根据具体的场景和需求，选择是否使用 KMP 算法。
评论