Trie : 高效的存储和查找字符串集合的数据结构
#include<iostream>
using namespace std;
const int N=1e5+10;
int s[N][26],cnt[N],idx;
/*
s[p][u]=++idx
p : 当前节点的位置 u : 当前的字母 ++idx : 上一个节点的位置
*/
char str[N];
void insert(char *str)
{
int p=0; //0是根节点,树从根节点开始
for(int i=0;str[i];i++) //遍历字符串,因为字符串以/0结尾
{
int u=str[i]-'a'; //将输入的字母转化为数字
if(!s[p][u]) s[p][u]=++idx;
p=s[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(!s[p][u]) return 0; //没查到说明没有这个字符串
p=s[p][u];
}
return cnt[p]; //输出以p位置为结尾的字符串数量
}
int main()
{
int m;
cin>>m;
while(m--)
{
char op[2];
//char数组存储字符串要多开一位用来存储/0,开数组是为了过滤空格
scanf("%s%s",&op,&str);
if(*op=='I') insert(str);
//数组的名字就是数组里第一个元素的地址,对数组取地址会得到第一个元素
else printf("%d\n",query(str));
}
return 0;
}