kmp模式匹配算法代码

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个文本串中查找一个模式串的出现位置。下面是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_partial_match_table(text, pattern, table):
        text_len = len(text)
        pattern_len = len(pattern)
        text_index = 0
        pattern_index = 0
        while text_index < text_len:
            if text[text_index] == pattern[pattern_index]:
                if pattern_index == pattern_len - 1:
                    return text_index - pattern_index
                text_index += 1
                pattern_index += 1
            elif pattern_index > 0:
                pattern_index = table[pattern_index - 1]
            else:
                text_index += 1
        return -1

    # 主函数调用
    if not text or not pattern or len(pattern) > len(text):
        return -1
    table = build_partial_match_table(pattern)
    return match_with_partial_match_table(text, pattern, table)