KMP 的 next 数组到底在算什么

常青 已验证 最后核对 2026-11-21

一句话结论

next[i] 是模式串前 i+1 个字符中最长的相等真前缀与真后缀长度,也就是前缀函数 π(i)。它回答的是「失配时已匹配部分还有多长可以复用」。

为什么(原理)

朴素匹配失配时整体右移一位,丢掉了已匹配的信息。若已匹配部分的前缀与后缀相同,这段后缀必然是下一轮的前缀,右移「已匹配长度 − π(已匹配长度−1)」位即可跳过无效比较。

以 ABABACA 为例逐个前缀求值:

i子串最长相等真前后缀π(i)
0A无0
1AB无0
2ABAA1
3ABABAB2
4ABABAABA3
5ABABAC无0
6ABABACAA1
ABABACA 的 next 数组逐位推导单步执行

怎么做(命令与配置)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def prefix_function(p: str) -> list[int]:
    n = len(p)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]
        if p[i] == p[j]:
            j += 1
        pi[i] = j
    return pi

验证方式与预期输出

1
2
assert prefix_function("ABABACA") == [0, 0, 1, 2, 3, 0, 1]
assert prefix_function("AAAA") == [0, 1, 2, 3]

两条断言都过才算对;AAAA 专挑「只写 if 不写 while」的错误。

踩坑

  • 不少教材的 next 是 π 左移一位再减 1(即 [-1, ...]),与 π 不是同一套定义,混用会在 j = next[j] 处打转。
  • 索引语义要统一:pi[i] 表示长度还是下标,混了就差一位。

延伸思考

π 数组本质是「字符串与自身的相似度」,与 Z 函数可互转,也是很多题用哈希替代 KMP 的底气。

用 Obsidian 写,用 Git 存,用 Hugo 发布。
使用 Hugo 构建