KMP 入门：next 数组存的不是玄学，是最长相等前后缀

KMP 入门：next 数组存的不是玄学，是最长相等前后缀

一、KMP 难，不是因为代码长

字符串匹配里，KMP 经常被认为难背。真正难点不是代码，而是next或lps数组含义不清。很多人把它当成“失败后跳到哪里”的魔法表，背完很快忘。

KMP 的核心是利用已经匹配过的信息。模式串前面一段和后面一段相等时，匹配失败后不用从头开始。lps[i]表示模式串前 i+1 个字符中，最长的相等真前缀和真后缀长度。

二、失败时跳转的是已知相等结构

假设已经匹配到模式串位置 j，下一位失败。前面 j 个字符已经和文本匹配。此时可以把模式串移动到最长前后缀对齐的位置。

flowchart TD A[已匹配前缀] --> B[下一字符失败] B --> C[查 lps[j-1]] C --> D[模式串回退到较短前缀] D --> E[继续比较]

这不是跳过可能答案，而是利用前后缀相等证明跳过的那些位置不可能成功。

三、先写清 lps 构造

下面是 Python 版本。变量名用length表示当前最长前后缀长度。

def build_lps(pattern: str) -> list[int]: lps = [0] * len(pattern) length = 0 i = 1 while i < len(pattern): if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 elif length > 0: length = lps[length - 1] else: lps[i] = 0 i += 1 return lps

回退时不是length -= 1，而是跳到lps[length - 1]。这一步最容易写错。

四、匹配过程也只是在复用 lps

文本匹配时，i 走文本，j 走模式。匹配成功一起走，失败时 j 回退到 lps[j-1]。j 为 0 再失败，i 才前进。

KMP 的时间复杂度是 O(n+m)，因为 i 不回退，j 的回退总次数也被前进次数摊销。证明复杂度时不能只说“显然快”。

最后，KMP 适合单模式串匹配。多模式串要看 Trie 或 AC 自动机。别拿一个模板打所有字符串题。

KMP 还要注意空模式串和重复字符。aaaaa这类模式会让 lps 连续增长，也是检验构造逻辑的好样本。很多错误实现只在普通字符串上通过，遇到重复字符就回退错。

匹配到完整模式后，j 不一定归零，而是回退到lps[j-1]，这样可以处理重叠匹配。比如在aaaa中找aa，答案不止两个不重叠位置。题目要求是否允许重叠，要先读清。

最后，复杂度证明可以用“i 不回退，j 总回退次数有限”解释。不要只背 O(n+m)。能说明为什么不会退成 O(nm)，才算真正理解 KMP。

KMP 的调试也有技巧。先打印 pattern 和 lps，对照每个位置的最长前后缀。很多错误不在匹配过程，而在 lps 构造。lps 错了，后面所有跳转都会跟着错。

还要区分不同 next 定义。有些教材的 next 存的是长度，有些存的是回退下标，有些还会整体右移。题解必须先说明采用哪一种定义。定义不统一，是 KMP 学习混乱的主要来源之一。

五、总结

KMP 的 lps 数组表示最长相等真前后缀，不是玄学跳转表。失败时回退，是因为已经匹配的信息证明某些位置不可能成功。理解这个不变量后，代码就不需要硬背。字符串算法先讲清结构，再谈模板。