Trie 树CSP-S

💡 核心思想

Trie（前缀树/字典树）是一种树形数据结构，每条边代表一个字符，从根到某节点的路径上的字符组成一个字符串。支持 $O(|s|)$ 的插入、查询和前缀匹配。变体包括 01-Trie（处理异或问题）。

🎯 直觉理解

Trie 就像一本字典的目录结构。所有以 "ab" 开头的单词共享 "a→b" 这个前缀路径，然后在 "b" 后面根据下一个字母分叉。查找某个前缀是否出现过，只需要沿路径走一遍就行。

📝 算法流程

1. 插入：沿字符路径走，不存在则创建新节点
2. 查询：沿路径走，走不到则不存在
3. 每个节点维护 son[26] 和 end 标记
4. 01-Trie：son[2]，处理二进制位

$$\text{Trie 空间：} O(\text{总字符数} \times |\Sigma|)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int trie[1000005][26], tot = 1;
bool End[1000005];
void insert(const string& s) {
    int p = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[p][ch]) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    End[p] = true;
}
bool search(const string& s) {
    int p = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[p][ch]) return false;
        p = trie[p][ch];
    }
    return End[p];
}
int main() {
    int n; cin >> n;
    while (n--) {
        string op, s; cin >> op >> s;
        if (op == "insert") insert(s);
        else cout << (search(s) ? "Yes" : "No") << "\n";
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目