AcWing | Trie字符串统计

朴灿烈づ我的快乐病毒、 2022-12-19 06:23 141阅读 0赞

**题目内容：**

> 维护一个字符串集合，支持两种操作：
> 
>     “I x”向集合中插入一个字符串x；
>     “Q x”询问一个字符串在集合中出现了多少次。
> 
> 共有N个操作，输入的字符串总长度不超过 10万，字符串仅包含小写英文字母

**输入格式**

> 第一行包含整数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

**思路：** 就是建树，每个节点是一个字母，具体的见代码。

**完整代码：**

#include<iostream>
    using namespace std;
    const int N=100010;
    int son[N][26];//26是指 每个节点最多有26个子节点
    int cnt[N];//以当前字符结尾的单词个数
    int idx;//当前使用的下标,下标是0的点即是根节点也是空节点
    char str[N];
    void insert(char str[]){ 
        int p=0;
        for(int i=0;str[i];i++){ //遍历字符串，字符串末尾是/0多以可以用str[i]直接判断是不是结尾了
            int u=str[i]-'a';//把26个字母映射到0-25
            if(!son[p][u])son[p][u]=++idx;//如果p这个节点不存在u子节点的话 就要把他创建出来
            p=son[p][u];//向前走
        }
        cnt[p]++;//以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 n;
        scanf("%d",&n);
        while(n--){ 
            char op[2];
            scanf("%s%s",op,str);
            if(op[0]=='I')insert(str);
            else printf("%d\n",query(str));
        }
        return 0;
    }