0Pricing
Coding Interview Prep · 课时

KMP 前缀函数

在 O(n + m) 内查找模式

KMP 前缀函数 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 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 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「KMP 前缀函数」这节课中我会学到什么？

在 O(n + m) 内查找模式 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

「KMP 前缀函数」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. KMP 前缀函数
  2. 多项式字符串哈希
  3. 用于模式搜索的 Z 函数
  4. 使用字典树进行前缀查找
← 返回 Coding Interview Prep