trie树

维护一个字符串集合，支持两种操作：

“I x”向集合中插入一个字符串x；
“Q x”询问一个字符串在集合中出现了多少次。

共有N个操作，输入的字符串总长度不超过

输入格式

第一行包含整数N，表示操作数。

接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。

输出格式

对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。

每个结果占一行。

数据范围

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1


##########################################################################

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 1e5+10;
 5 int son[N][24], flag[N], idx;
 6 
 7 void insert(char* str){
 8     int p = 0;//p 是一个指针，第一次指向根节点
 9     for(int i = 0;str[i];++i){
10         int u = str[i] - 'a';
11         if(son[p][u] == 0) 
12             son[p][u] = ++idx;//创建一个新的节点（++idx）,指编号为p的那个节点它指向的u那个节点的指针是idx
13         p = son[p][u];//指向新节点
14     }
15     flag[p]++;//做标记
16 }
17 int query(char* str){
18     int p = 0;
19     for(int i = 0;str[i];++i){
20         int u = str[i] - 'a';
21         if(son[p][u]) p = son[p][u];
22         else return 0;
23     } 
24     return flag[p];
25 }
26 int main(){
27     int n;
28     cin >> n;
29     char op[2];
30     char str[N];
31     while(n--){
32         cin >> op >> str;
33         if(*op == 'I'){
34             insert(str);
35         }else{
36             cout << query(str) << endl;
37         }
38     }
39     return 0;
40 }

View Code

end