题目描述

Trie字符串统计(高效地存储和查找字符串集合的数据结构)

Trie树：先输入有关数据，构成有内容的数，再在其中查找字符串

必须所查字符串的最后一个字母也是树的最后一个节点时才算找到

样例

输入
7
I abc
Q abc
Q abc
Q ab
I ab
I ab
Q ab

输出
1
1
0
2

C++ 代码

#include<iostream>
using namespace std;
const int N=100010;
//son[][]代表子节点，[N]表示当前枝的第N个结点，[26]表示该结点的子节点代表的字母
//cnt[N]表示当前节点出现的次数
//idx表示子节点的序号
int son[N][26],cnt[N],idx;

//字符串
char str[N];

void insert(char stk[])
{
    int p=0;     //从根节点出来的结点序号
    for(int i=0;str[i];i++)      //字符串的最后一个是\0,控制循环终止
    {
        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];
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char op[2];
        scanf("%s%s",op,str);
        if(op[0]=='I')insert(str);
        else cout<<query(str)<<endl;
    }
    return 0;
}