AcWing 835. Trie字符串统计
原题链接
简单
作者:
我是java同学
,
2022-12-11 19:54:07
,
所有人可见
,
阅读 113
#include <iostream>
using namespace std;
const int N = 100010;
int idx, son[N][26], cnt[N];
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;
else p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
cin >> n;
while (n --)
{
char op[2];
cin >> op >> str;
if (op[0] == 'I') insert(str);
else cout << query(str) << endl;
}
return 0;
}