KMP 入门next 数组存的不是玄学是最长相等前后缀一、KMP 难不是因为代码长字符串匹配里KMP 经常被认为难背。真正难点不是代码而是next或lps数组含义不清。很多人把它当成“失败后跳到哪里”的魔法表背完很快忘。KMP 的核心是利用已经匹配过的信息。模式串前面一段和后面一段相等时匹配失败后不用从头开始。lps[i]表示模式串前 i1 个字符中最长的相等真前缀和真后缀长度。二、失败时跳转的是已知相等结构假设已经匹配到模式串位置 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(nm)因为 i 不回退j 的回退总次数也被前进次数摊销。证明复杂度时不能只说“显然快”。最后KMP 适合单模式串匹配。多模式串要看 Trie 或 AC 自动机。别拿一个模板打所有字符串题。KMP 还要注意空模式串和重复字符。aaaaa这类模式会让 lps 连续增长也是检验构造逻辑的好样本。很多错误实现只在普通字符串上通过遇到重复字符就回退错。匹配到完整模式后j 不一定归零而是回退到lps[j-1]这样可以处理重叠匹配。比如在aaaa中找aa答案不止两个不重叠位置。题目要求是否允许重叠要先读清。最后复杂度证明可以用“i 不回退j 总回退次数有限”解释。不要只背 O(nm)。能说明为什么不会退成 O(nm)才算真正理解 KMP。KMP 的调试也有技巧。先打印 pattern 和 lps对照每个位置的最长前后缀。很多错误不在匹配过程而在 lps 构造。lps 错了后面所有跳转都会跟着错。还要区分不同 next 定义。有些教材的 next 存的是长度有些存的是回退下标有些还会整体右移。题解必须先说明采用哪一种定义。定义不统一是 KMP 学习混乱的主要来源之一。五、总结KMP 的 lps 数组表示最长相等真前后缀不是玄学跳转表。失败时回退是因为已经匹配的信息证明某些位置不可能成功。理解这个不变量后代码就不需要硬背。字符串算法先讲清结构再谈模板。