链式结构的字符串匹配代码

链式结构的字符串匹配，比如KMP算法，其核心代码可以分为以下几个步骤：

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

def kmp_search(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    prefix_func = compute_prefix_function(pattern)
    j = 0
    for i in range(text_len):
        while j > 0 and text[i] != pattern[j]:
            j = prefix_func[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == pattern_len:
            # 找到匹配，返回起始位置
            return i - pattern_len + 1
    return -1  # 没有找到匹配

# 使用示例
text = "ABABDABACDABABC"
pattern = "ABACDAB"
match_index = kmp_search(text, pattern)

这个代码中，`compute_prefix_function`计算了失配函数，`kmp_search`则是实际的匹配过程。在匹配过程中，如果发现字符不匹配，会通过失配函数更新主串的位置，而非简单地回退到上一个字符，以此提高效率。