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[j]。
代码如下：

1. def compute_prefix_function(pattern):
2.     """计算部分匹配表 (prefix table)"""
3.     prefix_table = [0] * len(pattern)
4.     j = 0  # 代表前缀的索引
6.     for i in range(1, len(pattern)):
7.         # 如果字符不匹配，寻找新的 j
8.         while j > 0 and pattern[i] != pattern[j]:
9.             j = prefix_table[j - 1]
10.         
11.         # 如果字符匹配，j 加 1
12.         if pattern[i] == pattern[j]:
13.             j += 1
14.         
15.         # 更新 prefix table
16.         prefix_table[i] = j
17.    
18.     return prefix_table
20. def kmp_search(text, pattern):
21.     """KMP 字符串匹配算法"""
22.     prefix_table = compute_prefix_function(pattern)
23.     print(prefix_table)
24.     j = 0  # 模式串的起始位置
26.     for i in range(len(text)):
27.         # 如果字符不匹配，使用 prefix table 回溯 j
28.         while j > 0 and text[i] != pattern[j]:
29.             j = prefix_table[j - 1]
30.         
31.         # 如果字符匹配，j 加 1
32.         if text[i] == pattern[j]:
33.             j += 1
34.         
35.         # 如果模式串匹配完毕，返回匹配起始位置
36.         if j == len(pattern):
37.             return i - j + 1  # 返回匹配起始索引
38.         
39.         # 如果没有匹配到，继续下一轮循环
40.     return -1  # 未找到匹配
42. # 示例使用
43. if __name__ == "__main__":
44.     text = "ABABDABACDABABCABAB"
45.     pattern = "ABABCABAB"
46.     result = kmp_search(text, pattern)
47.    
48.     if result != -1:
49.         print(f"Pattern found at index {result}")
50.     else:
51.         print("Pattern not found in the text")

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。