kmp算法 - ToB企服应用市场:ToB评测及商务社交产业平台

KMP算法，全称为Knuth-Morris-Pratt算法，是一种字符串匹配算法。它的根本头脑是，当出现字符串不匹配时，可以知道一部分文本内容是一定匹配的，可以利用这些信息避免重新匹配已经匹配过的文本。这种算法的时间复杂度为O(n+m)，此中n是文本串的长度，m是模式串的长度，比暴力匹配算法具有更高的效率。KMP算法的核心是利用模式串自己的特点，预处理出一个next数组，用于在匹配过程中快速移动模式串。

def compute_prefix_function(pattern):
"""计算部分匹配表 (prefix table)"""
prefix_table = [0] * len(pattern)
j = 0 # 代表前缀的索引
for i in range(1, len(pattern)):
# 如果字符不匹配，寻找新的 j
while j > 0 and pattern[i] != pattern[j]:
j = prefix_table[j - 1]
# 如果字符匹配，j 加 1
if pattern[i] == pattern[j]:
j += 1
# 更新 prefix table
prefix_table[i] = j
return prefix_table
def kmp_search(text, pattern):
"""KMP 字符串匹配算法"""
prefix_table = compute_prefix_function(pattern)
print(prefix_table)
j = 0 # 模式串的起始位置
for i in range(len(text)):
# 如果字符不匹配，使用 prefix table 回溯 j
while j > 0 and text[i] != pattern[j]:
j = prefix_table[j - 1]
# 如果字符匹配，j 加 1
if text[i] == pattern[j]:
j += 1
# 如果模式串匹配完毕，返回匹配起始位置
if j == len(pattern):
return i - j + 1 # 返回匹配起始索引
# 如果没有匹配到，继续下一轮循环
return -1 # 未找到匹配
# 示例使用
if __name__ == "__main__":
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
result = kmp_search(text, pattern)
if result != -1:
print(f"Pattern found at index {result}")
else:
print("Pattern not found in the text")

复制代码