字典树

16 Nov 2025

1. 简介

字典树（Trie，也叫前缀树）是一种专门处理字符串的数据结构。它把字符串按字符逐层存储：从根节点出发，沿着边经过的字符连接起来，就是一个前缀。

例如插入 cat 和 car 时，两个单词会共用 c → a 这段路径，然后分别走向 t 和 r。因此，Trie 能自然地保存大量具有相同前缀的字符串。

对于只包含小写字母的字符串，每个节点通常保存 26 条子边：next[u][0] 到 next[u][25]，分别表示下一个字符为 a 到 z。根节点通常编号为 1。

2. 插入与前缀信息

插入一个字符串时，从根节点开始，逐个读取字符。如果当前字符对应的子节点不存在，就新建一个节点；然后走到该子节点。字符串读完后，在最后一个节点记录“有多少字符串在这里结束”。

for (char c : s) {
    int id = c - 'a';
    if (!next[u][id]) next[u][id] = ++nodeCount;
    u = next[u][id];
}
endCount[u]++;

endCount[u] 很重要：它表示有多少个字符串恰好在节点 u 结束。若输入中有重复字符串，也应累加，而不是只记录一个布尔值。

Trie 的插入和查询时间都与字符串长度成正比。若所有字符串的总长度为 L，建树的总时间通常是 O(L)。

3. 例题：洛谷 P10470 前缀统计

给定 N 个字符串 S，每次查询给定一个字符串 T，要求统计有多少个 S 是 T 的前缀。

先把所有 S 插入 Trie。查询 T 时，从根节点沿着 T 的字符向下走。每到达一个节点，就把该节点的 endCount 加入答案，因为在这里结束的字符串正好是 T 的一个前缀。

如果某一步对应的子节点不存在，说明后面的字符不可能再匹配，当前累计值就是答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000 + 10;
int nextNode[N][26];
int endCount[N];
int nodeCount = 1;

void insert(const string& s) {
    int u = 1;
    for (char c : s) {
        int id = c - 'a';
        if (!nextNode[u][id]) nextNode[u][id] = ++nodeCount;
        u = nextNode[u][id];
    }
    endCount[u]++;
}

int query(const string& t) {
    int u = 1;
    int answer = 0;

    for (char c : t) {
        int id = c - 'a';
        if (!nextNode[u][id]) break;
        u = nextNode[u][id];
        answer += endCount[u];
    }
    return answer;
}

int main() {
    int n, m;
    cin >> n >> m;

    while (n--) {
        string s;
        cin >> s;
        insert(s);
    }

    while (m--) {
        string t;
        cin >> t;
        cout << query(t) << '\n';
    }
    return 0;
}

例如插入 at、ate、cat 后，查询 ateam 时，at 和 ate 都是它的前缀，答案为 2；查询 cat 时，答案为 1。

Trie 的核心不是记住固定模板，而是明确每个节点代表一个前缀，并根据题意决定节点还要保存什么信息：字符串结束次数、经过次数、子树大小或某种标记。这样，许多字符串前缀问题都可以沿着一条树上路径在线性时间内解决。

字典树

Related Posts