什么是字典树

字典树(Trie Tree) 是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
——百度 · 百科

它是一种高效存储和查找字符串集合的树形结构，核心思想是利用公共前缀共享路径，从而减少重复比较，实现快速的前缀匹配与检索。

实现

可以定义字典树的结构如下：

struct trie {
    bool end = 0; //是否以当前字母结尾
    int count=0; //公共前缀的数量
    unordered_map<char,trie> ch; //子树
};

添加

void add(trie &tr,string s){
    tr.count++;
    if(s.length()==0){
        tr.end=1;
        return;
    }
    add(tr.ch[s[0]],s.substr(1));
}

前缀数量查找

ll  ask(trie &tr,string s){
    if(s.length()==0){
        return tr.count;
    }
    if(tr.ch.count(s[0])){
        return ask(tr.ch[s[0]],s.substr(1));
    }
    return 0;
}

单词查找

bool check(trie &tr,string s){
    if(s.length()==0){
        return tr.end;
    }
    if(tr.ch.count(s[0])){
        return check(tr.ch[s[0]],s.substr(1));
    }
    return 0;
}

示例

P8306 【模板】字典树

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

struct trie {
    bool end = 0;
    int count=0;
    unordered_map<char,trie> ch;
};

void add(trie &tr,string s){
    tr.count++;
    if(s.length()==0){
        tr.end=1;
        return;
    }
    add(tr.ch[s[0]],s.substr(1));
}

ll  ask(trie &tr,string s){
    if(s.length()==0){
        return tr.count;
    }
    if(tr.ch.count(s[0])){
        return ask(tr.ch[s[0]],s.substr(1));
    }
    return 0;
}

int main() { 
    ll t;
    cin>>t;
    while(t--){
        ll n,q;
        cin>>n>>q;
        trie tr;
        while(n--){
            string s;
            cin>>s;
            add(tr,s);
        }
        while(q--){
            string s;
            cin>>s;
            cout<<ask(tr,s)<<endl;
        }
    }
    return 0;
}