Trie树算法

Trie树，也称为前缀树或字典树，是一种特殊的树型数据结构。它用于存储一组字符串，使得查找、插入和删除字符串的操作非常高效。类似这种，

模板：

这是用数组来模拟上图中的树的结构，逻辑上和上图结构一致。

大家一定要手动看代码模拟一边，只靠想象不光浪费时间还想不明白。

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点，这里0号点指的是idx
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
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];
}