跳到主要内容

匹配与字典树解题框架

本节目标

用 KMP 复用已匹配前缀，用 Trie 共享单词前缀。

当问题反复比较一个模式串，或反复查询许多单词的共同前缀时，逐字符重来会浪费已经得到的信息。KMP 将模式串内部的可复用前后缀写入 nxt；Trie 则把一批单词共同的路径合并为一棵树。

识别信号​

  • 在长文本中找模式串的全部出现位置，且重叠出现也要计数；
  • 失配后仍可能复用已经匹配的一部分前缀；
  • 需要连续插入和查询单词，查询既有“是否为完整单词”也有“是否具有此前缀”；
  • 多个字符串共享较长开头，逐个比较会重复扫描相同字符。

问题模型与核心不变量​

KMP 扫描主串时，matched 表示当前主串后缀与模式串前缀已经相等的长度。失配后主串指针不回退，而是把 matched 回退到更短、仍可能成立的相等前后缀长度。

Trie 的每条边表示一个字符，根到某个节点的路径表示一个前缀。节点的终止标记独立于路径是否存在：路径能走到只说明该前缀出现过，只有终止标记为真才说明它是已插入的完整单词。

通用模板​

构建模式串的 nxt：nxt[i] 是 pattern[0..i] 的最长相等真前后缀长度
从左到右扫描主串：失配时 matched 回退到 nxt[matched - 1]
完整匹配后记录起点，并再次回退 matched 以保留重叠匹配
Trie 插入：沿字符创建缺失节点，末尾标记 isWord
完整查询：路径存在且末尾 isWord 为真
前缀查询：只要求路径存在

模板变体​

  • KMP 的 nxt 可用于单次匹配、统计出现次数和处理重叠子串；若模式串固定、文本持续到达，也可保留当前 matched 状态继续扫描。
  • Trie 可以把子节点从小写字母数组替换为哈希映射，以适应更大的字符集；节点还可附加计数、词频或最短词等信息。
  • 只查询一个模式串时，KMP 的预处理成本是线性的；大量单词共享前缀时，Trie 的公共路径能减少重复存储与比较。

母题序列​

按必学顺序练习：

  1. KMP 字符串：用 nxt 在失配后复用模式串前缀。
  2. 实现 Trie（前缀树）：区分前缀路径和完整单词的终止标记。

常见误区​

  • KMP 完整匹配后把 matched 直接清零，会漏掉重叠出现的位置。
  • 将 nxt[i] 当作“下一个跳转下标”，混淆了它作为相等前后缀长度的含义。
  • Trie 查询 app 时，只因 apple 路径存在就返回完整单词成功，遗漏终止标记检查。
  • 插入单词时没有只在末尾标记，导致所有前缀都被误判为完整单词。

迁移方向​

字符串匹配还可迁移到多模式匹配与自动机；前缀树可迁移到字典序枚举、单词拆分、异或字典树和带权前缀查询。它们的共同点都是把“已经匹配或已经走过的结构”保存下来，避免再次从头比较。