AcWing 835. Trie字符串统计
原题链接
简单
作者:
825532446
,
2024-01-22 18:59:37
,
所有人可见
,
阅读 34
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int son[N][26],cnt[N],idx;//下标为0的点,既是根节点,也是空节点 cnt是count的缩写
char str[N];
void insert(char *str)
{
int p=0;
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];
}
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
char op[2];
scanf("%s%s", op, str);
if (*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}