$Trie$树：高效的存储和查找字符串的集合的数据结构

$Trie$树存储的字符串，范围都不会很大，比如都是小写字母，都是大写字母，都是数字等。那他怎么存呢?

假如要存一堆单词，比如$acwing$，$acchat$，$akcspj$和$iakioi$。我们需要

1. 由于$Trie$树是树，所以得先创建根节点。
   
2. 存入第一个单词，要从头到尾依次存入每一个字母。
   
3. 创建后面的单词，如果当前节点没有遍历到的字母就创建，有就往下走。
   
   因为前面都是“ac”，到后面就不一样了，所以从“c”那开始分叉。
   
   这两个也都遵循规律，最后$Trie$树就长成了这么个形式。

最后，我们是要给每个结尾都标记一下，意思是以标记结尾处有一个单词，比如要是再插入“ac”这个单词会跟之前的重复，这时要是不标记一下，根本就识别不出这有个单词。

很简单的就结束了。

模版

题目

int son[N][字符串中字符的范围]，cnt[N], idx; // 下标是0的点，既是根节点，又是空节点

插入操作：

void insert(char str[]){
    int p = 0;
    for (int i = 0; str[i]; i++){
        int u = str[i] - ('a'或'A'或'0'或其他东西);
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

查询操作：

int query(char str[]){
    int p = 0;
    for (int i = 0; str[i]; i++){
        int u = str[i] - ('a'或'A'或'0'或其他东西);
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

没啦！