Trie树

// Trie树用于快速存储和查找字符串集合


int son[N][26], cnt[N], idx;
/* 
0号点既是根节点，又是空节点
son[][]存储树中每个节点的子节点, 第一维表示树的总结点数, 第二维表示每个结点最多有几个子结点
son中存储的是数字
cnt[]存储以每个节点结尾的单词数量
Trie树在每一个单词的结尾打上一个标记便于查找
*/

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    // str[i] 判断是否到了字符串的结尾
    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];
}