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 在第二个字符就岔开。

2 · 第二步：查询一个串——区分完整 word / 前缀 / 不在字典

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