kmp算法
1、kmp算法介绍KMP算法，全称为Knuth-Morris-Pratt算法，是一种字符串匹配算法。它的根本头脑是，当出现字符串不匹配时，可以知道一部分文本内容是一定匹配的，可以利用这些信息避免重新匹配已经匹配过的文本。这种算法的时间复杂度为O(n+m)，此中n是文本串的长度，m是模式串的长度，比暴力匹配算法具有更高的效率。KMP算法的核心是利用模式串自己的特点，预处理出一个next数组，用于在匹配过程中快速移动模式串。
KMP算法的实现过程可以分为两个步调：预处理和匹配。预处理阶段，必要对模式串举行分析，得到next数组。匹配阶段，将模式串移动到精确的位置举行匹配。
2、计算next数组
对要匹配的pattern字符串：ABABCABAB求next数组。
结果为【0，0，1，2，0，1，2，3，4】.
A：【0】
AB：【0，0】
ABA：【0，0，1】
ABAB：【0，0，1，2】
ABABC：【0，0，1，2，0】
ABABCA：【0，0，1，2，0，1】
ABABCAB：【0，0，1，2，0，1，2】
ABABCABA：【0，0，1，2，0，1，2，3】
ABABCABAB：【0，0，1，2，0，1，2，3，4】
3、求匹配的字符串
对字符串举行匹配，当pattern字符串和text中出现不匹配的位置时，将text中的下标往右边移动next。
代码如下：
def compute_prefix_function(pattern):
"""计算部分匹配表 (prefix table)"""
prefix_table = * len(pattern)
j = 0# 代表前缀的索引
for i in range(1, len(pattern)):
# 如果字符不匹配，寻找新的 j
while j > 0 and pattern != pattern:
j = prefix_table
# 如果字符匹配，j 加 1
if pattern == pattern:
j += 1
# 更新 prefix table
prefix_table = 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 != pattern:
j = prefix_table
# 如果字符匹配，j 加 1
if text == pattern:
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")
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]