kmp算法Python

KMP算法全称Knuth-Morris-Pratt算法，是一种用于字符串匹配的高效算法。它通过构建部分匹配表（也称为失配函数或最长公共前后缀长度），避免了传统暴力匹配中的回溯操作，提高了搜索效率。在Python中，我们可以按照以下步骤实现KMP算法：

1. 定义部分匹配表（P）：计算每个模式字符前缀和后缀的最长公共前后缀长度，用于指导搜索过程。

2. 创建模式字符串S，并初始化匹配指针i和模式指针j。

3. 当j小于模式长度时，比较S[i]和S[j]：
- 如果它们相等，i 和 j 都加一；
- 如果它们不相等：
- 如果j>0，从P[j]开始检查是否能跳过当前不匹配的位置，找到合适的偏移量；
- 如果存在，将j设置为对应的偏移量；
- 否则，i增加1。

4. 搜索结束后，如果i等于原始字符串S的长度，说明找到了一个匹配；否则，没有找到匹配。

下面是简单的Python代码示例：

def get_next(pattern):
    next_table = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = next_table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        next_table[i] = j
    return next_table

def kmp_search(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    next_table = get_next(pattern)
    i, j = 0, 0
    
    while i < text_len:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        elif j > 0:
            j = next_table[j - 1]
        else:
            i += 1
    return j == pattern_len

# 使用示例
text = "ABABDABACDABABC"
pattern = "ABACD"
if kmp_search(text, pattern):
    print(f"Pattern '{pattern}' found in text.")
else:
    print(f"Pattern '{pattern}' not found in text.")