0Pricing
Competitive Programming Academy · 课时

使用字典树进行前缀查找

快速存储并查询单词前缀

使用字典树进行前缀查找 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

巧妙地存储单词

字典树是一种通过共享公共前缀来存储单词的树。它能极快地处理前缀查询。🌳

为什么不只使用集合

集合可以查询完整单词，但字典树还可以回答前缀查询，例如是否有单词以 pre 开头。

节点和边

每个节点表示某个单词中的一个位置，每条边则标有从根节点出发的路径上的一个字符。

用字典表示子节点

在 Python 中，最简单的节点是一个字典，将字符映射到对应的子节点。简洁而灵活。

root = {}

插入单词

要插入单词，就逐个遍历字符；每当缺少对应的子节点时，就创建一个。

node = root
for c in word:
    node = node.setdefault(c, {})

标记单词结尾

插入完成后，设置一个结尾标记，这样就能区分完整单词和普通前缀。

node['#'] = True

搜索完整单词

要搜索单词，就沿着字符逐个查找；如果某一步缺失，则该单词不存在。之后还要检查结尾标记。

for c in word:
    if c not in node:
        return False
    node = node[c]

检查前缀

前缀查询执行相同的遍历，但不需要检查结尾标记。到达最后一个节点就表示查询成功。

时间复杂度

插入和查找的代价都是O(L)，其中 L 是单词长度，与您存储了多少个单词无关。起作用的是长度。

按前缀统计单词

在每个节点存储一个计数，就能立即回答有多少个已存储单词共享给定前缀。

字典树的用武之地

字典树可以用于自动补全、词典检查，以及针对位的 XOR 最大值问题。它是竞赛字符串题中的常用工具。

快速检查

确认一次字典树查找实际需要多少代价。

回顾：字典树入门完成

现在您可以构建字典树，在 O(L) 时间内插入和搜索，并快速回答前缀和计数查询。🌟

常见问题解答

「使用字典树进行前缀查找」课时是免费的吗？

是的 — 「使用字典树进行前缀查找」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「使用字典树进行前缀查找」这节课中我会学到什么？

快速存储并查询单词前缀 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

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

「使用字典树进行前缀查找」课时需要多长时间？

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

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

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

此课程中的所有课时

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