用数据结构代码表示KMP算法

KMP算法，全称为Knuth-Morris-Pratt算法，是一种高效的字符串匹配算法，用于在一个文本串中查找指定模式串的所有位置。它利用了部分匹配表（也称作失配函数或最长公共前后缀），通过避免回溯，提高了搜索效率。

以下是使用Python的数据结构（字典）来构建KMP失配函数的一个简单示例：

def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0  # 当前已匹配的字符长度
    j = 1  # 已计算的部分匹配表索引

    while j < len(pattern):
        if pattern[j] == pattern[length]:
            length += 1
            lps[j] = length
            j += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[j] = 0
                j += 1
    
    return lps

# 使用失配函数进行匹配
def kmp_search(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    lps = build_lps(pattern)

    i = 0  # 文本指针
    j = 0  # 模式指针
    matches = []

    while i < text_len:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        elif j != 0:
            j = lps[j - 1]
        else:
            i += 1
    
    if j == pattern_len:
        matches.append(i - pattern_len)  # 如果完全匹配，则记录起始位置
    return matches

# 示例
text = "ABABDABACDABABC"
pattern = "ABCDAB"
print(kmp_search(text, pattern))

在这个例子中，`build_lps` 函数创建了失配函数 `lps`，而 `kmp_search` 则利用这个函数进行匹配，并返回所有匹配的位置。