KMP算法的代码

KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。它的核心思想是利用已经匹配过的信息，尽可能减少比较次数。

下面是KMP算法的Python代码实现：

def kmp_search(pattern, text):
    """
    KMP算法实现字符串匹配
    :param pattern: 模式串
    :param text: 文本串
    :return: 匹配成功的位置列表
    """
    m, n = len(pattern), len(text)
    if m == 0 or n == 0 or m > n:
        return []

    # 计算模式串的next数组
    next = get_next(pattern)

    i, j = 0, 0
    res = []
    while i < n:
        if j == m - 1 and pattern[j] == text[i]:
            # 匹配成功，记录匹配位置
            res.append(i - j)
            # 继续匹配下一个
            j = next[j]
        if text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = next[j]
            if j == -1:
                i += 1
                j += 1

    return res


def get_next(pattern):
    """
    计算模式串的next数组
    :param pattern: 模式串
    :return: next数组
    """
    m = len(pattern)
    next = [-1] * m
    i, j = 0, -1
    while i < m - 1:
        if j == -1 or pattern[i] == pattern[j]:
            i += 1
            j += 1
            next[i] = j
        else:
            j = next[j]

    return next

其中，get_next函数用于计算模式串的next数组，而kmp_search函数则是主要的匹配函数，它遍历文本串，通过比较文本串和模式串的字符来推进匹配过程，并利用next数组来跳过已经匹配过的字符。最终，该函数返回所有匹配成功的位置列表。

下面是一个简单的测试：

text = "ABCABCABCABD"
pattern = "ABCABD"
res = kmp_search(pattern, text)
print(res)  # [6]

以上代码输出了模式串在文本串中出现的位置。