字典树（Trie）

问题引入

给定一个字符串集合，需要频繁执行「插入一个串」「查询某串是否存在」「查询某前缀是否出现过」「枚举所有以某前缀开头的串」等操作。把所有串存进 set 或哈希表，精确查找虽快，但前缀查询只能遍历所有键逐一比对，$10^5$ 量级即超时。关键在于：这些查询都围绕公共前缀展开——字典树（Trie，又称前缀树） 把公共前缀压缩到同一条路径上，使前缀相关操作降至 $O(L)$（$L$ 为串长）。

核心思想：用树表示公共前缀

每条从根到某节点的路径对应一个字符串前缀，路径上的边标记字符。根代表空串，每个节点可选地标记为「单词结尾」（isEnd）。共享前缀的串复用同一段路径，故插入 "cat" 后再插入 "car" 只需新增 r 一个节点。

插入 "cat"、"car"、"dog" 后的 Trie：

          root
          /  \
         c    d
         |    |
         a    o
        / \   |
       t   r  g
       ★   ★  ★

★ 表示单词结尾标记 isEnd

四个核心操作：

• insert(s)：从根出发，逐字符向下走，缺边则新建节点，末节点置 isEnd。
• search(s)：沿字符走完 $s$，要求末节点 isEnd 为真。
• startsWith(p)：沿字符走完 $p$，能走通即可（不要求 isEnd）。
• enumerate(p)：定位到 $p$ 对应节点，DFS 子树收集所有单词。

单次插入/查找均为 $O(L)$，与集合大小无关。

基本实现与三种存储

每个节点需保存「子节点映射」与「结尾标记」。子节点映射有三种存储方式，权衡速度、空间与字符集灵活性。

数组存储（固定小字符集）

字符集为 26 个小写字母时，每个节点开 children[26]，下标直接由 ch - 'a' 得到，$O(1)$ 转移、缓存友好。这是 LeetCode 风格的默认写法。

struct TrieNode {
    TrieNode* children[26] = {};  // 缺省 nullptr
    bool isEnd = false;           // 是否为单词结尾
};

class Trie {
    TrieNode* root = new TrieNode();
    // 沿 s 走到末节点；中途断链返回 nullptr
    TrieNode* find(const string& s) {
        TrieNode* cur = root;
        for (char ch : s) {
            int c = ch - 'a';
            if (!cur->children[c]) return nullptr;
            cur = cur->children[c];
        }
        return cur;
    }
public:
    void insert(string word) {
        TrieNode* cur = root;
        for (char ch : word) {
            int c = ch - 'a';
            if (!cur->children[c])
                cur->children[c] = new TrieNode();
            cur = cur->children[c];
        }
        cur->isEnd = true;
    }
    bool search(string word) {
        TrieNode* node = find(word);
        return node && node->isEnd;
    }
    bool startsWith(string prefix) {
        return find(prefix) != nullptr;
    }
};

哈希表存储（任意字符集）

字符集较大或离散（Unicode、句子）时，用 unordered_map<char, Node*> 代替数组，按需分配，避免 26 倍浪费：

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

转移代价略高（哈希常数），但空间与字符集解耦。其余逻辑与数组版完全一致，把 children[c] 换成 children.count(c) / children[c] 即可。

全局二维数组（竞赛常用）

固定上界 + 全局数组 + 自由函数，无需 new、无指针开销，是竞赛最常见写法：

const int MAXN = 1e6 + 10;          // 节点总数上限
int trie[MAXN][26], cnt;            // cnt：已用节点数
bool isEnd[MAXN];

void insert(const string& s) {
    int u = 0;                      // 0 号节点为根
    for (char ch : s) {
        int c = ch - 'a';
        if (!trie[u][c]) trie[u][c] = ++cnt;
        u = trie[u][c];
    }
    isEnd[u] = true;
}

bool search(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!trie[u][c]) return false;
        u = trie[u][c];
    }
    return isEnd[u];
}

bool startsWith(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!trie[u][c]) return false;
        u = trie[u][c];
    }
    return true;
}

要点：MAXN 须大于「所有串总长度」；多组数据时每次 memset 重置已用部分或维护版本号，否则残留状态污染结果。

复杂度

设 $L$ 为串长、$\Sigma$ 为字符集大小、$N$ 为所有串总长度。

操作	时间	空间
insert	$O(L)$	—
search / startsWith	$O(L)$	—
总空间	—	$O(N\cdot\Sigma)$（数组）/ $O(N)$（哈希）

注意空间是 Trie 的主要代价：数组版每个节点占 $\Sigma$ 个指针，稀疏时浪费严重；哈希版按需分配但常数更大。共享前缀越多越省，串彼此无公共前缀时退化为 $O(N)$ 节点。

完整模板

类模板附带单词计数与「前缀出现次数」，支持基本删除（递归清理无分支节点）：

struct TrieNode {
    TrieNode* children[26] = {};
    int pass = 0;   // 经过此节点的单词数（前缀计数）
    int end = 0;    // 以此节点结尾的单词数
};

class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(const string& s) {
        TrieNode* cur = root;
        cur->pass++;
        for (char ch : s) {
            int c = ch - 'a';
            if (!cur->children[c])
                cur->children[c] = new TrieNode();
            cur = cur->children[c];
            cur->pass++;
        }
        cur->end++;
    }
    // s 作为完整单词的出现次数
    int countWords(const string& s) {
        TrieNode* cur = root;
        for (char ch : s) {
            int c = ch - 'a';
            if (!cur->children[c]) return 0;
            cur = cur->children[c];
        }
        return cur->end;
    }
    // 以 p 为前缀的单词数
    int countPrefix(const string& p) {
        TrieNode* cur = root;
        for (char ch : p) {
            int c = ch - 'a';
            if (!cur->children[c]) return 0;
            cur = cur->children[c];
        }
        return cur->pass;
    }
    // 删除一个 s：沿途 pass--、末节点 end--
    void erase(const string& s) {
        if (countWords(s) == 0) return;
        TrieNode* cur = root;
        cur->pass--;
        for (char ch : s) {
            int c = ch - 'a';
            TrieNode* nxt = cur->children[c];
            nxt->pass--;
            if (nxt->pass == 0) {       // 该分支不再有单词
                cur->children[c] = nullptr;
                return;                 // 后续节点随内存回收
            }
            cur = nxt;
        }
        cur->end--;
    }
};

pass（前缀计数）是 Trie 最常用的附加信息：自动补全、词频、删除判空都依赖它。erase 采用「计数归零即断链」的惰性回收，简单可靠；若需立即释放内存，可递归 delete 孤立子树。

经典示例

实现 Trie（LeetCode 208）

即上文基本实现，三函数 insert / search / startsWith，不再赘述。

添加与搜索单词 - 通配符（LeetCode 211）

支持 . 匹配任意字符。遇到 . 时 DFS 尝试所有子节点，靠 Trie 的树形结构天然剪枝：

struct TrieNode {
    TrieNode* children[26] = {};
    bool isEnd = false;
};

class WordDictionary {
    TrieNode* root = new TrieNode();
    bool dfs(TrieNode* node, const string& s, int i) {
        if (i == s.size()) return node->isEnd;
        char ch = s[i];
        if (ch != '.') {
            int c = ch - 'a';
            return node->children[c] &&
                   dfs(node->children[c], s, i + 1);
        }
        for (int c = 0; c < 26; ++c)    // 通配：枚举所有子节点
            if (node->children[c] &&
                dfs(node->children[c], s, i + 1))
                return true;
        return false;
    }
public:
    void addWord(string word) {
        TrieNode* cur = root;
        for (char ch : word) {
            int c = ch - 'a';
            if (!cur->children[c])
                cur->children[c] = new TrieNode();
            cur = cur->children[c];
        }
        cur->isEnd = true;
    }
    bool search(string word) {
        return dfs(root, word, 0);
    }
};

通配符搜索的最坏复杂度为 $O(26^L)$，但 Trie 提供的实际分支远少于 26，绝大多数输入下可接受。

单词搜索 II（LeetCode 212）

在字符网格中找出所有出现在字典中的单词。朴素做法对每个单词独立 DFS 网格，超时。关键优化：把所有单词建成一棵 Trie，DFS 网格时同步沿 Trie 下行，一旦无对应边即剪枝。

struct TrieNode {
    TrieNode* children[26] = {};
    string word;   // 叶子处存完整单词，命中即收集
};

class Solution {
    TrieNode* root = new TrieNode();
    int m, n;
    void dfs(vector<vector<char>>& board, int i, int j,
             TrieNode* node, vector<string>& ans) {
        char ch = board[i][j];
        if (ch == '#' ||
            !node->children[ch - 'a']) return;   // 越界或无此分支
        node = node->children[ch - 'a'];
        if (!node->word.empty()) {              // 命中一个单词
            ans.push_back(node->word);
            node->word.clear();                 // 去重，避免重复
        }
        board[i][j] = '#';                      // 标记已访问
        int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
        for (int k = 0; k < 4; ++k) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n)
                dfs(board, ni, nj, node, ans);
        }
        board[i][j] = ch;                       // 回溯
    }
public:
    vector<string> findWords(vector<vector<char>>& board,
                             vector<string>& words) {
        for (auto& w : words) {                 // 所有单词建 Trie
            TrieNode* cur = root;
            for (char ch : w) {
                int c = ch - 'a';
                if (!cur->children[c])
                    cur->children[c] = new TrieNode();
                cur = cur->children[c];
            }
            cur->word = w;
        }
        m = board.size(); n = board[0].size();
        vector<string> ans;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                dfs(board, i, j, root, ans);
        return ans;
    }
};

命中后清空 word 是关键去重手段：同一单词只收集一次。Trie 在此扮演「多模式匹配的剪枝骨架」——共享前缀的单词只需探索一次网格路径。

替换单词（LeetCode 648）

把句子中每个单词替换为字典中存在的最短词根。把词根建 Trie，对每个单词沿 Trie 下行，首个 isEnd 节点即为最短词根：

struct TrieNode {
    TrieNode* children[26] = {};
    bool isEnd = false;
};

class Solution {
    TrieNode* root = new TrieNode();
    string rootOf(const string& word) {
        TrieNode* cur = root;
        string prefix;
        for (char ch : word) {
            int c = ch - 'a';
            if (!cur->children[c]) return word;  // 无词根，原样返回
            prefix += ch;
            cur = cur->children[c];
            if (cur->isEnd) return prefix;       // 命中最短词根
        }
        return word;
    }
public:
    string replaceWords(vector<string>& dict,
                        string sentence) {
        for (auto& r : dict) {                   // 词根建 Trie
            TrieNode* cur = root;
            for (char ch : r) {
                int c = ch - 'a';
                if (!cur->children[c])
                    cur->children[c] = new TrieNode();
                cur = cur->children[c];
            }
            cur->isEnd = true;
        }
        string ans, word;
        stringstream ss(sentence);
        bool first = true;
        while (ss >> word) {
            if (!first) ans += ' ';
            ans += rootOf(word);
            first = false;
        }
        return ans;
    }
};

「沿 Trie 下行取首个结尾」正是前缀树最自然的操作——哈希表无法在 $O(L)$ 内完成最短前缀匹配。

字典中最长单词（LeetCode 720）

求字典中可由「逐字母添加」构成的最长单词：每步所加字母须使中间串都在字典中，同长取字典序最小。把所有单词建 Trie，从根 BFS，只走 isEnd 为真的节点（保证每一步都构成字典中存在的单词），按字典序升序遍历，首次到达更深的即为答案：

struct TrieNode {
    TrieNode* children[26] = {};
    bool isEnd = false;
};
class Solution {
public:
    string longestWord(vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (auto& w : words) {            // 建 Trie
            TrieNode* cur = root;
            for (char ch : w) {
                int c = ch - 'a';
                if (!cur->children[c])
                    cur->children[c] = new TrieNode();
                cur = cur->children[c];
            }
            cur->isEnd = true;
        }
        string ans;
        queue<pair<TrieNode*, string>> q;
        q.push({root, ""});
        while (!q.empty()) {               // BFS 逐层扩展
            auto [node, s] = q.front(); q.pop();
            if (s.size() > ans.size()) ans = s;
            for (int c = 0; c < 26; ++c) { // 升序保证同长取最小
                if (node->children[c] &&
                    node->children[c]->isEnd)
                    q.push({node->children[c],
                            s + char('a' + c)});
            }
        }
        return ans;
    }
};

isEnd 在此充当「可达性闸门」：只有沿途每一段都是真实单词的路径才允许继续延伸，确保答案可由逐字母添加构成。BFS 保证最先到达的最大深度即最长，字典序升序遍历保证同长取最小。

自动补全系统（LeetCode 642）

用户逐字符输入，实时返回以当前输入为前缀、热度最高的 3 个句子。Trie 中每个节点维护子树句子，输入到达前缀节点后 DFS 子树收集并按热度排序：

struct Node {
    unordered_map<char, Node*> ch;
    string word;        // 以此节点结尾的句子
    int freq = 0;
};

class AutocompleteSystem {
    Node* root = new Node();
    Node* cur = root;   // 当前已输入前缀所在节点
    string input;       // 当前输入累积串
    void insert(const string& s, int times) {
        Node* p = root;
        for (char c : s) {
            if (!p->ch[c]) p->ch[c] = new Node();
            p = p->ch[c];
        }
        p->freq += times;
        p->word = s;
    }
    void collect(Node* p,
                 vector<pair<int,string>>& out) {
        if (!p) return;
        if (p->freq > 0)
            out.push_back({-p->freq, p->word});  // 负热度便于排序
        for (auto& [c, q] : p->ch) collect(q, out);
    }
public:
    AutocompleteSystem(vector<string>& sent,
                       vector<int>& times) {
        for (int i = 0; i < sent.size(); ++i)
            insert(sent[i], times[i]);
    }
    vector<string> inputChar(char c) {
        if (c == '#') {                  // 句子结束，记录并重置
            insert(input, 1);
            input.clear();
            cur = root;
            return {};
        }
        input += c;
        if (!cur || !cur->ch.count(c)) {
            cur = nullptr;               // 无此前缀，后续皆空
            return {};
        }
        cur = cur->ch[c];
        vector<pair<int,string>> cand;
        collect(cur, cand);              // 收集前缀子树全部句子
        sort(cand.begin(), cand.end());  // -freq 升序=热度降序
        vector<string> ans;
        for (int i = 0; i < (int)cand.size() && i < 3; ++i)
            ans.push_back(cand[i].second);
        return ans;
    }
};

维护 cur 指针随输入下移，避免每次重新从根遍历前缀。子树收集在输入串足够长时子树已很小，实测可接受；若需更优，可在每个节点预存 top-3 列表，插入时沿途更新。

01-Trie（二进制字典树）

把整数按二进制位（从高到低）视作字符插入 Trie，每位只有 0/1 两种转移，便得到 01-Trie。它把「数的大小关系」转化为「路径分支」，专门求解异或极值类问题。

核心贪心：求与 $x$ 异或最大的数时，从高位起每位优先选与 $x$ 当前位相反的分支（使该位异或结果为 1），不存在才选相同分支。

以 3 位二进制、插入 $4=100$ 与 $5=101$ 为例：

  root
   |1
   ●
   |0
   ●
  / \
0●   ●1
(4)  (5)

查询与 $x=4=100$ 异或最大的数，从高位起贪心取相反位：

• b2：$x$ 的位为 1，想走 0–无 0 分支，只能走 1。
• b1：$x$ 的位为 0，想走 1–无 1 分支，只能走 0。
• b0：$x$ 的位为 0，想走 1–存在 1 分支，走 1，该位异或得 1。

走到 $5$，$4\oplus5=1$，即两数最大异或值。

数组中两数最大异或（LeetCode 421）

把所有数插入 01-Trie，再对每个数查询最大异或：

class Solution {
    int trie[200010 * 31][2], cnt = 0;
    void insert(int x) {
        int u = 0;
        for (int i = 30; i >= 0; --i) {  // 从高到低
            int b = (x >> i) & 1;
            if (!trie[u][b]) trie[u][b] = ++cnt;
            u = trie[u][b];
        }
    }
    int maxXor(int x) {                  // 找与 x 异或最大的数
        int u = 0, res = 0;
        for (int i = 30; i >= 0; --i) {
            int b = (x >> i) & 1;
            int want = b ^ 1;            // 贪心取相反位
            if (trie[u][want]) {
                res |= (1 << i);
                u = trie[u][want];
            } else {
                u = trie[u][b];
            }
        }
        return res;
    }
public:
    int findMaximumXOR(vector<int>& nums) {
        memset(trie, 0, sizeof trie);
        cnt = 0;
        int ans = 0;
        for (int x : nums) {
            ans = max(ans, maxXor(x));   // 先查后插，避免与自身异或
            insert(x);
        }
        return ans;
    }
};

复杂度 $O(n\log V)$，$V$ 为值域。位序必须从高到低：高位 1 的价值大于低位所有位之和，贪心才成立。

最大异或子段和

子段 $a[l..r]$ 的异或和 $=p[r]\oplus p[l-1]$，其中 $p$ 为前缀异或（$p[0]=0$）。于是「最大异或子段」化为「前缀异或数组中两数最大异或」，复用上例：

int maxSubarrayXor(vector<int>& a) {
    // 复用 insert / maxXor（同 421）
    memset(trie, 0, sizeof trie);
    cnt = 0;
    insert(0);                // 空前缀 p[0]=0 必须先插入
    int pref = 0, ans = 0;
    for (int x : a) {
        pref ^= x;            // p[i] = p[i-1] ^ a[i]
        ans = max(ans, maxXor(pref));
        insert(pref);
    }
    return ans;
}

注意必须先插入 $p[0]=0$，否则无法表达「子段从下标 1 开始」的情形。

限制下最大异或（LeetCode 1707）

每次查询「$\le m$ 的数中与 $x$ 异或最大值」。$m$ 随查询变化，无法离线一次性建树。离线排序：查询按 $m$ 升序，数也按升序，随查询增量插入 $\le m$ 的数：

struct Query { int m, x, idx; };

vector<int> maximizeXor(vector<int>& nums,
                        vector<vector<int>>& Q) {
    sort(nums.begin(), nums.end());
    int n = Q.size();
    vector<Query> qs(n);
    for (int i = 0; i < n; ++i)
        qs[i] = {Q[i][1], Q[i][0], i};   // {m, x, idx}
    sort(qs.begin(), qs.end(),
         [](auto& a, auto& b){ return a.m < b.m; });
    // 01-Trie 的 insert / maxXor 同 421
    vector<int> ans(n, -1);
    int p = 0;
    for (auto& q : qs) {
        while (p < (int)nums.size() && nums[p] <= q.m)
            insert(nums[p++]);           // 按 m 增量插入
        if (p > 0) ans[q.idx] = maxXor(q.x);
    }
    return ans;
}

离线化是 Trie 题的常见套路：当约束（此处 $m$）单调变化时，把「在线查询」转为「按约束排序的增量插入」，避免可持久化的开销。

AC 自动机

Trie 解决「单模式串前缀」问题，AC 自动机（Aho-Corasick）在其上解决「多模式串匹配」——在文本中一次性找出所有模式串出现位置。本质是 Trie + KMP 的失配指针：为每个节点建一条 fail 边，指向「当前所表示前缀的最长真后缀，且该后缀也是某模式串前缀」的节点。匹配时沿文本走 Trie，失配则跳 fail，避免回退文本指针。

以模式串 “he”、“she” 为例：

 root
 /  \
s    h
|    |
h    e ★  ("he")
|
e ★      ("she")

fail 指针指向「最长且为某前缀的真后缀」：

• sh -> h：“sh” 的后缀 “h” 仍是前缀。
• she -> he：“she” 的后缀 “he” 是完整模式。

匹配文本 "she"：root→s→sh→she 命中 “she”，沿 fail 跳到 he 又命中 “he”–一次扫描同时报出两个模式，无需为每个模式独立查找。

构建与匹配模板

build 用 BFS 构造 fail，并把缺失边补成 fail 转移（Trie 图优化），使匹配时无需显式跳 fail：

const int MAXN = 1e6 + 10;
int ch[MAXN][26], fail[MAXN], cnt[MAXN], tot;

void insert(const string& s) {
    int u = 0;
    for (char c : s) {
        int x = c - 'a';
        if (!ch[u][x]) ch[u][x] = ++tot;
        u = ch[u][x];
    }
    cnt[u]++;              // 该节点为一个模式串结尾
}

void build() {
    queue<int> q;
    for (int c = 0; c < 26; ++c)
        if (ch[0][c]) q.push(ch[0][c]);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int c = 0; c < 26; ++c) {
            if (ch[u][c]) {
                fail[ch[u][c]] = ch[fail[u]][c];
                q.push(ch[u][c]);
            } else {
                ch[u][c] = ch[fail[u]][c];  // 缺失边补为 fail 转移
            }
        }
    }
}

int query(const string& s) {                 // 返回出现过的模式串种类数
    int u = 0, ans = 0;
    for (char c : s) {
        u = ch[u][c - 'a'];                   // trie 图下直接转移
        for (int v = u; v && cnt[v] != -1; v = fail[v]) {
            ans += cnt[v];
            cnt[v] = -1;                      // 标记已统计，防重复
        }
    }
    return ans;
}

fail 的构造利用了「父节点 fail 已就绪」的性质：ch[u][c] 的 fail 即 ch[fail[u]][c]。Trie 图把所有缺失边指向 fail 对应转移后，query 中 u = ch[u][c] 一步到位，无需 while 循环跳 fail。

AC 自动机适用于「文本 + 多模式串」场景。单模式串用 KMP 即可；多模式串 + 多文本且需在线则需 AC 自动机的更复杂变体（如后缀自动机、广义后缀树）。

可持久化 01-Trie

普通 01-Trie 在插入新数时会修改原有路径，无法回溯历史版本。可持久化的核心：每次插入只新建「被修改路径」上的节点，其余子树通过指针共享旧版本。于是版本 $i$ 保存前 $i$ 个数的 Trie，利用两版本相减即可查询任意区间。

以「查询 $a[l..r]$ 中与 $x$ 异或的最大值」为例：版本 $r$ 减版本 $l-1$，即用 siz[r] - siz[l] 判断某分支在区间内是否存在。

const int MAXN = 300010, B = 23;
int ch[MAXN * 24][2], siz[MAXN * 24];
int root[MAXN], cnt;

int insert(int pre, int x) {        // 旧版本 pre 上插入 x，返回新根
    int cur = ++cnt, rt = cur;
    for (int i = B; i >= 0; --i) {
        int b = (x >> i) & 1;
        ch[cur][b] = ++cnt;          // 走向 b 的儿子新建
        ch[cur][!b] = ch[pre][!b];   // 另一儿子继承旧版本
        siz[cur] = siz[pre] + 1;
        pre = ch[pre][b];
        cur = ch[cur][b];
    }
    siz[cur] = siz[pre] + 1;         // 叶子
    return rt;
}

int query(int l, int r, int x) {     // a[l..r] 中与 x 异或最大值
    l = root[l - 1]; r = root[r];
    int res = 0;
    for (int i = B; i >= 0; --i) {
        int b = (x >> i) & 1, want = b ^ 1;
        if (siz[ch[r][want]] - siz[ch[l][want]] > 0) {
            res |= 1 << i;
            l = ch[l][want]; r = ch[r][want];
        } else {
            l = ch[l][b]; r = ch[r][b];
        }
    }
    return res;
}

// 主流程：root[0] = 0（空 Trie）
// for i = 1..n: root[i] = insert(root[i-1], a[i]);
// 查询 (l, r, x)：query(l, r, x)

每个版本新增 $B+1$ 个节点，总空间 $O(nB)$。siz 充当「版本差」的计数器，使 Trie 具备了线段树般的区间可减性——这是可持久化数据结构的共同范式。

横向对比

场景	Trie	哈希表	其他
精确查找	$O(L)$	$O(L)$ 平均 $O(1)$	各有适用场景
前缀查询	$O(L)$ 原生支持	不支持，需遍历键	—
字典序遍历	先序遍历即有序	需额外排序	平衡树亦可
通配符/正则	DFS 天然支持	不支持	—
多模式匹配	AC 自动机 $O(n+m)$	不适用	KMP 仅单模式
异或极值	01-Trie $O(n\log V)$	不适用	—
空间	共享前缀省，稀疏浪费	紧凑	—

判别要点：

• 前缀 vs 精确：只需精确查找用哈希表更省空间；任何前缀相关操作（补全、最短词根、前缀计数）优先 Trie。
• 静态 vs 动态：模式串集合固定时 AC 自动机一次建树；需动态增删模式串则维护 Trie + fail 增量更新。
• 异或 vs 大小：求异或极值用 01-Trie；求第 $k$ 小/大用可持久化 01-Trie 或权值线段树。
• 区间 vs 全局：单次全局查询用普通 Trie；需查询任意历史区间用可持久化 Trie。

常见陷阱

1. 忘记标记 isEnd：search 会把仅作为前缀的串误判为完整单词。
2. 节点数开小：数组版 trie[N][26] 的 $N$ 须按「所有串总长度」估算，01-Trie 须按「数个数 $\times$ 位数」估算。
3. 字符集未归一：大写、数字、Unicode 未先映射到连续下标，越界或哈希冲突。
4. 01-Trie 位序错误：必须从高位到低位插入与查询，否则贪心失效。
5. 01-Trie 未清空：多组数据共用全局数组时未 memset 或重置 cnt，残留脏数据。
6. 最大异或与自身：查询前未插入自身可避免，或在插入后再查询时排除同位置。
7. AC 自动机 fail 构建顺序错：必须 BFS 保证父节点 fail 先就绪；ch[u][c] 的 fail 依赖 ch[fail[u]][c]。
8. AC 自动机重复计数：同一节点沿 fail 链多次统计；统计后置 -1 标记或使用 last 优化跳链。
9. Word Search II 重复收集：命中单词后未清空 word，同一单词被多次加入答案。
10. 可持久化原地修改：可持久化 Trie 必须为每个版本新建路径节点，复用旧节点会被后续版本污染。
11. 以为 Trie 能做任意子串匹配：Trie 只擅长前缀；子串匹配需 AC 自动机（多模式）或后缀结构（单文本多模式）。

小结

字典树把公共前缀压缩为共享路径，使插入、查找与前缀相关操作均降至 $O(L)$。其价值不在精确查找（哈希表已足够），而在前缀查询、多模式匹配与异或极值三大场景：

1. 识别：前缀补全 / 最短词根 / 前缀计数 / 多模式匹配 / 异或极值 → 优先考虑 Trie。
2. 选型：固定小字符集用数组版；任意字符集用哈希版；竞赛用全局二维数组。异或问题用 01-Trie，多模式匹配用 AC 自动机，区间查询用可持久化 Trie。
3. 扩展：AC 自动机 = Trie + 失配指针，把单模式 KMP 推广到多模式；可持久化 01-Trie 借「版本相减」获得区间可减性，与可持久化线段树同构。