Trie字典树

TTrie树又称字典树，前缀树。是一种可以高效查询前缀字符串的树，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。`做题看到大量字符串或者大量字符就往Trie树或者哈希这边想，因为速度很快.

结构图如下：

代码

const int N = 1e5 + 10;
int son[N][26], cnt[N], idx;  // 下标0代表根节点和空节点，cnt用于计数，idx代表结点的索引
char str[N];
void insert(char* str)
{
    int p = 0;  // 根节点
    for (int i = 0; str[i]; ++i) {
        int u = str[i] - 'a';  // 映射字母a-z为0-25
        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-z为0-25
        if (!son[p][u]) return 0;  // 没有该子结点就返回查询不到
        p = son[p][u];  // 走到该子节点
    }  
    return cnt[p];  // 返回该子节点存在的单词个数    
}