acwing 835. Trie字符串统计

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

一般用trie ，题目限制了字符种类26个或者52个。

如果想在trie 中保存下面一组字符串，原理如下：

abcdef、abdef、aced、bcdf、bcff、cdaa、bcdc

存储：

一般来说，会在所有结尾的单词标记一下，不然在有可能重复的地方找不到该单词。

查找：
直接进行一层一层下来找，如果有在trie树中以查找字符串结束的字符，则true，反之，false。

题目：

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。
共有 N 个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

输入格式
第一行包含整数 N，表示操作数。

接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围
1≤N≤2∗104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1

思路：

1. trie 的构造
2. 每个节点唯一标识
3. 每个字符串结尾都有标志，保存数量

code:

#include <iostream>

using namespace std;

const int N = 100010;

// son[N][26] : N 表示有N层
// 每个节点的最多26， cnt表示 以第N个节点结尾字符串的个数，idx表示索引
int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[])
{
    
    int p = 0;
    for(int i=0; str[i]; i++)   // char str[]以'\0' 结尾，可以这样弄
    {
    
        int u = str[i] - 'a';  // 映射到0 -25
        if(!son[p][u]) son[p][u] = ++idx;  // 如果不存在，创建出来，每个节点唯一编号
        p = son[p][u];
    }
    cnt[p] ++;   // 以这个点结尾的数量 + 1 
}

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()
{
    
    int m;
    cin >> m;
    
    while(m --)
    {
    
        char op[2];
        cin >> op >> str;
        if(op[0] == 'I')  insert(str);
        else cout << query(str) << endl;
    }
    return 0;
}