Trie · prefix tree

Trie：把一组词按公共前缀叠成树

Naive matching、KMP、Boyer-Moore、Rabin-Karp 都在一段 text 里查找一个 pattern。换一个场景：有大量 word（字典、自动补全候选、敏感词表），要反复问「这个串是不是某个 word？」「有没有 word 以它开头？」。把所有 word 逐字符插进同一棵树——共享公共前缀走同一条路径，这就是 Trie(prefix tree)。查询一个长度 L 的串只需顺着边走 L 步，和字典里有多少个 word 无关。

1 · 逐词插入与前缀合并

从 root 出发，沿 word 的每个字符往下：有这条边就复用，没有就新建节点。word 的最后一个字符落点标成词尾 ●（虚线环）。注意 to / tea / ted 怎样共享 $t\to e$ 这段，而 to 在第二个字符就岔开。

图 1-1 · 逐词插入 Trie，公共前缀自动合并成同一条路径。可改词表观察树形变化。

节省的来源：把 N 个 word 放入一个朴素列表，判断「是否存在」需逐个比较；Trie 把它们的公共前缀只存一份，查询代价只看被查串自身的长度。代价是空间——每个不同前缀都占节点，字母表大时更明显。

2 · 查询的三种结局

从 root 沿 query 逐字符走。三种结局：其一中途无边可走 → 这个前缀根本不在字典；其二走到底但落点不是词尾 → 它只是某些 word 的前缀（自动补全正是利用这点列出后续）；其三走到底且落点是词尾 ● → 命中一个完整 word。

图 2-1 · 查询一个串并区分三种结局：完整 word、仅为前缀、不在字典。可改查询串对照三者。

三种结局各有一个例子：te 走到底是前缀而非词尾，tea 命中完整 word，tex 在 x 处无边可走、查询失败。Trie 是 Aho-Corasick 的骨架——给它加上 failure link，就能一遍扫描 text 同时找出全部 word。