AcWing 835. Trie字符串统计
原题链接
简单
作者:
梦溪
,
2022-04-27 10:43:04
,
所有人可见
,
阅读 124
按照字符串每一位的二进制作为子节点构造Tire
理论上任何字符都可以存(不是)
时间复杂度 $O(n)$
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx; // 下标是0的点,既是根节点,又是空节点
char str[N];
void insert(char str[]) {
int p = 0;
for (int i = 0; str[i]; i ++) {
int u = str[i];
while (u) {
if (!son[p][u & 1])
son[p][u & 1] = ++ idx;
p = son[p][u & 1];
u = u >> 1;
}
}
cnt[p] ++;
}
int query(char str[]) {
int p = 0;
for (int i = 0; str[i]; i ++) {
int u = str[i];
while (u) {
if (!son[p][u & 1])
return 0;
p = son[p][u & 1];
u = u >> 1;
}
}
return cnt[p];
}
int main() {
int n;
scanf("%d", &n);
while (n --) {
char op[2];
scanf("%s%s", op, str);
if (op[0] == 'I')
insert(str);
else
printf("%d\n", query(str));
}
return 0;
}