AcWing 835. Trie字符串统计
原题链接
简单
作者:
从前
,
2021-05-20 20:27:00
,
所有人可见
,
阅读 242
#include<iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N];
char str[N];
int idx = 0;
//关键是这个son二维数组,p表示父亲,u表示p的下一个点;
void insert(char *str) {
int p = 0;
for(int i = 0; str[i]; i++) {
int u = str[i] - '0';
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] - '0';
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;
}