字典树(Tire)

Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高

可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子:
1 –> 4 –> 8 –> 12 表示的就是字符串 caa 。
trie树的结构

trie 的结构非常好懂，我们用s[u,c]表示结点u的c字符指向的下一个结点，或着说是结点u代表的字符串后面添加一个字符c形成的字符串的结点。（c的取值范围和字符集大小有关，不一定是0~26.）
有时需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。

trie树的性质

• 根节点不包含字符，除根节点外的每一个子节点都包含一个字符
• 从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同

应用场景
典型应用是用于统计，排序和公共字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。
1)、检索字符串
字典树最基础的应用——查找一个字符串是否在“字典”中出现过。
2)、ac自动机
3)、维护异或信息

实现
这里我们采用数组实现的方式,需要准备一些东西

1. 定义一个son[][]数组,存储树中每个节点的子节点
2. 定义一个cnt[]数组,存储以每个节点结尾的单词数量
3. 定义一个idx,表示用到了哪个结点

有了以上东西后,我们就可以来构建一个trie树了,trie树的两个核心操作是插入,查询
插入

代码实现

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        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';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

例题
ACwing 835. Trie字符串统计

ac代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=20010;
int son[N][26],cnt[N],idx,n;
char str[N];
void insert(char *str)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        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';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main()
{
    cin >> n;
    while(n--)
    {
        char op[2];
        scanf("%s%s",op,str);
        if(*op=='I') insert(str);
        else cout << query(str) << endl;
    }
    return 0;
}