KMP 前缀函数
在 O(n + m) 内查找模式
KMP 前缀函数 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
模式匹配问题
您想要找出一个较小的模式在一段较长文本中的出现位置。朴素检查速度很慢，因此竞赛题通常要求使用更聪明的扫描方法。🔍
朴素搜索为何效率低
在每个位置比较模式可能需要O(n*m)的时间。在较大的输入上，这会悄悄超出时间限制。
认识前缀函数
前缀函数会在每个位置记录既是前缀又是后缀的最长真前缀长度。它是 KMP 的核心。
真前缀与后缀
真前缀或后缀不包含字符串本身。对于 ababa，最长的匹配前后缀长度为 3，即 aba。
pi[i] 保存什么
我们将这些值存储在一个名为pi的数组中。这里的 pi[i] 是以索引 i 结尾的切片所对应的最长前后缀长度。
一遍构建 pi
您可以从左到右构建pi，复用之前的值，而不是从头重新检查。复用正是整个技巧的关键。
def prefix_function(s):
pi = [0] * len(s)
return pi回退循环
当字符不匹配时，回退到pi[k-1]，而不是重置为零。这样可以避免重复工作。
while k > 0 and s[i] != s[k]:
k = pi[k - 1]延长匹配
如果当前字符匹配，就将长度加一并记录下来。当长度为零时发生不匹配，则保持为零。
if s[i] == s[k]:
k += 1
pi[i] = k使用这一技巧进行搜索
要在文本中搜索模式，请将它们拼接为pattern + sep + text。任何等于模式长度的 pi 值都表示找到了一次完整匹配。
combined = pattern + chr(0) + text
pi = prefix_function(combined)分隔符为何重要
分隔符是一个不出现在两个字符串中的符号。它可以防止匹配跨越拼接处，从而产生错误结果。
线性时间的收益
构建和搜索的时间复杂度都是O(n + m)。每个字符只会被处理一次，因此 KMP 可以应对规模巨大的竞赛输入。
快速检查
请检验您对前缀函数所记录内容的掌握程度。
回顾：KMP 概览
您已经学会了前缀函数：构建一次 pi，在不匹配时回退，并在线性时间内完成搜索。这就是 KMP 的核心。🎯
常见问题解答
「KMP 前缀函数」课时是免费的吗？
是的 — 「KMP 前缀函数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「KMP 前缀函数」这节课中我会学到什么？
在 O(n + m) 内查找模式 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「KMP 前缀函数」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- KMP 前缀函数
- 多项式字符串哈希
- 用于模式搜索的 Z 函数
- 使用字典树进行前缀查找