Python KMP算法
KMP算法（Knuth-Morris-Pratt算法）是一种用于在字符串中查找子字符串的高效算法，它利用了已匹配的部分信息来避免不必要的回溯。下面是一个示例代码，展示如何使用Python实现KMP算法：
def compute_lps(pattern):lps = [0] * len(pattern)j = 0i = 1while i < len(pattern):if pattern[i] == pattern[j]:j += 1lps[i] = ji += 1else:if j != 0:j = lps[j - 1]else:lps[i] = 0i += 1return lpsdef kmp_search(text, pattern):lps = compute_lps(pattern)i = 0j = 0while i < len(text):if text[i] == pattern[j]:i += 1j += 1if j == len(pattern):print("Pattern found at index", i - j)j = lps[j - 1]elif i < len(text) and text[i] != pattern[j]:if j != 0:j = lps[j - 1]else:i += 1# 测试示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)
在上面的示例中，compute_lps函数用于计算给定模式字符串的最长公共前缀和后缀的长度（LPS数组），而kmp_search函数则利用LPS数组来实现KMP算法的字符串匹配。在测试示例中，我们在文本字符串中搜索模式字符串，并打印出匹配的索引位置。
KMP算法的关键在于构建LPS数组，该数组可以帮助我们在匹配过程中跳过一些不必要的比较。这样可以提高字符串匹配的效率。