不妨设有字符串ab、abc、abd、ba,那么将建立如下的字典树。
#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx; // 26个字母,cnt存编号i下标的个数,下标0为空。
int 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;
p = son[p][u];
}
return cnt[p];
}
int main() {
scanf("%d", &n);
while(n -- ) {
char op[2]; // op[1]用于吞掉空格
scanf("%s%s", op, str);
if (op[0] == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁