数据结构：Trie树

题目描述

输入样例

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例

1
0
1

参考代码

#include <iostream>using namespace std;const int N = 100010;int son[N][26], cnt[N], idx;    // 下标是0的点既是根节点，又是空节点int m;
char op[2];
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", &m);while (m--){scanf("%s%s", op, str);if (op[0] == 'I') insert(str);else printf("%d\n", query(str));}return 0;
}