KMP 算法详解与 Python 代码实现 - 快速字符串匹配利器

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]

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