KMP算法,全称Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法。它通过预处理模式串,使得在匹配过程中,即使发生不匹配,也能从上一次匹配的位置继续进行,从而避免了从头开始匹配,大大提高了匹配效率。本文将带你从KMP算法的原理出发,一步步实现其源码,并实战演练。
KMP算法原理
KMP算法的核心思想是:当发生不匹配时,能够利用已经匹配的部分信息,避免从头开始匹配。具体来说,就是通过构建一个部分匹配表(也称为“失败函数”),记录模式串中每个位置之前的最大公共前后缀的长度。
构建部分匹配表
以模式串“ABCDABD”为例,构建其部分匹配表如下:
A B C D A B D
0 0 0 0 1 2 0
其中,第i列的值表示从模式串的第i个字符开始,到模式串的末尾,最长公共前后缀的长度。
匹配过程
在匹配过程中,如果发生不匹配,我们就可以利用部分匹配表来确定下一次匹配的起始位置。具体步骤如下:
- 将模式串与主串从左到右逐个比较。
- 如果比较的字符相同,则继续比较下一个字符。
- 如果比较的字符不同,则根据部分匹配表,将模式串右移,直到找到匹配的字符或者模式串的末尾。
KMP算法源码实现
下面是KMP算法的Python实现:
def kmp_search(text, pattern):
# 构建部分匹配表
def build_pmt(pattern):
pmt = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = pmt[j - 1]
if pattern[i] == pattern[j]:
j += 1
pmt[i] = j
return pmt
# 匹配过程
pmt = build_pmt(pattern)
i, j = 0, 0
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
return i - j
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = pmt[j - 1]
else:
i += 1
return -1
# 测试
text = "ABCDABDABCDABCDABDE"
pattern = "ABCDABD"
print(kmp_search(text, pattern)) # 输出:10
KMP算法实战演练
下面是一个使用KMP算法进行字符串匹配的实战案例:
def find_all_occurrences(text, pattern):
occurrences = []
index = kmp_search(text, pattern)
while index != -1:
occurrences.append(index)
index = kmp_search(text, pattern, index + 1)
return occurrences
# 测试
text = "ABCDABDABCDABCDABDE"
pattern = "ABCDABD"
print(find_all_occurrences(text, pattern)) # 输出:[10, 26]
通过以上实战案例,我们可以看到KMP算法在处理字符串匹配问题时,具有很高的效率。
总结
本文从KMP算法的原理出发,详细介绍了其构建过程和匹配过程,并通过Python代码实现了KMP算法。最后,通过实战案例展示了KMP算法在实际应用中的高效性。希望本文能帮助你更好地理解和掌握KMP算法。
