夜雨聆风学习资料网

ARTICLE · 1385580

字典树——模板 Trie

字典树——模板 Trie

一、什么是字典树

字典树(Trie),又叫前缀树,是一种专门用来处理字符串集合的树形数据结构。

它的核心思想很简单:把字符串一个字符一个字符地挂在树上,公共前缀只存一次。

有了这棵树,我们能很快做三件事:

  1. 插入一个字符串;

  2. 查询某个字符串是否出现过;

  3. 查询有多少个字符串以某个前缀开头。


二、字典树的核心功能

1. 节点长什么样

字典树上的每个节点代表"某个前缀",它需要存以下信息:

  • 它往下连的子节点(用 char → node* 的映射表示,走到哪个字符就跳到哪个子节点);

  • 一个 isEnd 标记,表示"有没有单词在这里结束";

  • 本题再加一个 cnt,表示"有多少个单词经过这个节点"。

cnt 是本题的关键。有了它,前缀查询就不用再往下遍历整棵子树,直接读节点上的 cnt 就行。

2. 插入(insert)

从根节点开始,一个字符一个字符往下走:

  • 如果当前字符对应的子节点不存在,就新建一个;

  • 然后走到这个子节点,把它的 cnt 加 1;

  • 走完整串后,把最后一个节点标记为 isEnd = true。

注意:cnt 加 1 的位置要放在跳到子节点之后,而不是新建节点的时候。这样哪怕是终点节点也会被计数。

3. 查找节点(findNode)

从根节点往下走,如果某个字符对应的子节点不存在,说明整棵树里没有这个前缀,返回空指针;否则一路走到最后一个字符,返回那个节点。

这个函数是单词查询、前缀查询的"公共底盘"。

4. 单词查询(search)

先找到单词的终点节点,再看它的 isEnd 是否为真。为真说明这个单词确实被插入过,否则只是某个更长单词的前缀。

5. 前缀查询(startWith)

先找到前缀的终点节点。如果节点不存在,返回 0;如果存在,直接返回它的 cnt。

比如插入 fusu 和 fusufusu 后,节点 fusu 的 cnt 是 2,所以查询前缀 fusu 就返回 2。


三、结合本题的思路

题目要求:给定 n 个模式串和 q 次询问,每次给一个文本串 t,问有多少个模式串以 t 为前缀。

思路很直接:

  1. 把所有模式串插入字典树,插入时沿途给每个节点的 cnt 加 1;

  2. 对每次询问,用 findNode 找到 t 的终点节点;

  3. 如果节点不存在,输出 0;如果存在,输出它的 cnt。

两点细节:

  • 题目里重复出现的模式串要分别计数(因为问的是"有多少个字符串 s_j"),所以不需要去重,cnt 直接累加就好;

  • 字符串总长最多 3×10⁶,字符集包含大小写字母和数字,用 unordered_map<char, node*> 比较通用。


四、参考代码

#include<bits/stdc++.h>using namespace std;struct node {    unordered_map<char, node*> child; // 子节点:字符 -> 子节点指针    bool isEnd;                        // 是否有单词在此结束    int cnt;                           // 经过当前节点的单词数    node() : isEnd(false), cnt(0) {}};// 插入一个单词,沿途维护 cntvoidinsert(node* root, const string& word){    node* cur = root;    for (char c : word) {        if (cur->child.find(c) == cur->child.end())            cur->child[c] = new node();        cur = cur->child[c];        ++cur->cnt;                    // 走到这个节点,计数加一    }    cur->isEnd = true;}// 找到字符串终点对应的节点,不存在返回 nullptrnode* findNode(node* root, const string& str){    node* cur = root;    for (char c : str) {        auto it = cur->child.find(c);        if (it == cur->child.end()) return nullptr;        cur = it->second;    }    return cur;}// 单词查询:判断某个单词是否被完整插入过boolsearch(node* root, const string& word){    node* p = findNode(root, word);    return p && p->isEnd;}// 前缀查询:返回以 pre 为前缀的单词数intstartWith(node* root, const string& pre){    node* p = findNode(root, pre);    return p ? p->cnt : 0;}intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    int T, n, q;    string s;    cin >> T;    while (T--) {        cin >> n >> q;        node* root = new node();        while (n--) { cin >> s; insert(root, s); }      // 插入全部模式串        while (q--) { cin >> s; cout << startWith(root, s) << '\n'; } // 逐次查询    }    return 0;}

五、几个容易踩的坑

  1. cnt 加 1 的位置:必须放在"跳到子节点之后"。如果放在"新建节点时加 1",那所有复用的旧路径都不会计数,答案会偏小。

  2. 别用 child.size() 当作前缀数量:child.size() 只是"直接子节点个数"。比如只插入 abc,查前缀 abc 时终点节点没有子节点,size() 是 0,但正确答案是 1。

  3. isEnd 和 cnt 分工不同:isEnd 管"这个单词是否存在",cnt 管"有多少单词以这段为前缀"。两者别混用。

#字典树#单词查询#前缀查询

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料