python实现kmp算法

KMP算法是一种用于字符串匹配的高效算法。下面是一个Python实现KMP算法的示例：

def kmp_search(text, pattern):
    # 构建部分匹配表
    def build_partial_match_table(pattern):
        table = [0] * len(pattern)
        prefix = 0
        suffix = 1
        while suffix < len(pattern):
            if pattern[prefix] == pattern[suffix]:
                prefix += 1
                table[suffix] = prefix
                suffix += 1
            elif prefix > 0:
                prefix = table[prefix - 1]
            else:
                table[suffix] = 0
                suffix += 1
        return table

    # 使用部分匹配表进行匹配
    def match_with_table(text, pattern, table):
        i = 0
        j = 0
        while i < len(text) and j < len(pattern):
            if text[i] == pattern[j]:
                i += 1
                j += 1
            elif j > 0:
                j = table[j - 1]
            else:
                i += 1
        if j == len(pattern):
            return True, i - len(pattern)
        else:
            return False, None

    # 调用辅助函数进行匹配
    table = build_partial_match_table(pattern)
    return match_with_table(text, pattern, table)

# 示例用法
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
result, index = kmp_search(text, pattern)
if result:
    print("Pattern found at index", index)
else:
    print("Pattern not found")

这段代码实现了KMP算法的核心逻辑。首先，通过`build_partial_match_table`函数构建部分匹配表，然后使用`match_with_table`函数进行匹配。最后，调用`kmp_search`函数进行字符串匹配。