AcWing 835. Trie字符串统计
原题链接
简单
作者:
szywdwd
,
2021-05-21 14:11:28
,
所有人可见
,
阅读 165
#include <iostream>
using namespace std;
const int MAX = 100010;
int son[MAX][26], idx;
int cnt[MAX];
void insert(char str[]) {
int p = 0;// 这个字符串在字典树里的下标,初始为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];// 字典树中以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;
cin >> N;
while(N--) {
char op[2];// 忽略输入的空格
cin >> op;
if(op[0] == 'I') {
char str[MAX];
cin >> str;
insert(str);
}
else if(op[0] == 'Q') {
char str[MAX];
cin >> str;
cout << query(str) << endl;
}
}
return 0;
}