KMP 算法

2026-05-02 暂无评论

全文共 472 字，阅读约 2 分钟

题目描述

给定一个文本串 s 和一个模式串 p，在 s 中查找 p 第一次出现的位置。如果不存在则返回 -1。

暴力匹配的时间复杂度为 O(m × n)，而 KMP 算法通过预处理模式串的"前后缀信息"，将匹配过程优化到 O(m + n)，核心思想是匹配失败时利用已知信息跳过不必要的比较。

解题方法：KMP（Knuth-Morris-Pratt）

KMP 算法的关键在于 next 数组（也称前缀函数）。它记录了模式串中每个位置之前的最长相等前后缀长度。当匹配失败时，模式串指针不回溯到开头，而是跳转到 next 数组指示的位置，从而避免重复匹配。

算法思路

构建 next 数组：遍历模式串，用双指针计算每个位置的最长相等前后缀长度。前缀指针 j 始终指向当前已匹配前缀的下一个位置，当字符匹配时 j 前移，不匹配时 j 回退到 nxt[j-1]。
匹配过程：遍历文本串，同样用双指针。字符匹配时模式串指针前移，不匹配时利用 next 数组回退。当模式串指针走到末尾，说明匹配成功。

代码解析

def build_next(patt):
    # 构建 next 数组（前缀函数）
    m = len(patt)
    nxt = [0] * m         # nxt[i] 表示 patt[:i+1] 的最长相等前后缀长度
    j = 0                 # 前缀指针
    for i in range(1, m): # i 是后缀指针
        # 不匹配时，前缀指针回退到前一个位置的 next 值
        while j > 0 and patt[i] != patt[j]:
            j = nxt[j - 1]
        # 匹配成功，前缀指针前移
        if patt[i] == patt[j]:
            j += 1
        nxt[i] = j
    return nxt


def kmp(s, p):
    # KMP 字符串匹配，返回 p 在 s 中首次出现的位置
    if not p:
        return 0
    nxt = build_next(p)
    j = 0                 # 模式串指针
    for i in range(len(s)): # 文本串指针
        # 不匹配时利用 next 数组回退
        while j > 0 and s[i] != p[j]:
            j = nxt[j - 1]
        if s[i] == p[j]:
            j += 1
        # 匹配完成
        if j == len(p):
            return i - len(p) + 1
    return -1


print(kmp("abababc", "ababc"))   # 输出: 2

代码要点说明

build_next：用模式串自己匹配自己的方式构建 next 数组。nxt[i] 记录 patt[:i+1] 的最长相等前后缀长度，i 从 1 开始，因为单个字符的前后缀长度为 0。
匹配回退：当 s[i] != p[j] 时，j = nxt[j - 1] 是关键一步。它利用已匹配部分的前后缀信息，将模式串向右滑动到合适位置，避免从头开始。
时间复杂度：构建 next 数组和匹配过程都是线性扫描，每个字符最多被比较两次。