【题目描述】

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

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

共有 N 个操作，输入的字符串总长度不超过 10⁵，字符串仅包含小写英文字母。

【输入格式】

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

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

【输出格式】

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

每个结果占一行。

【数据范围】

1≤N≤2∗10⁴

【输入样例】

5
I abc
Q abc
Q ab
I ab
Q ab

【输出样例】

1
0
1

Trie树，也叫前缀树或者字典树。

Trie 的结构非常好懂，我们用Trie[p][u]表示结点 p 的 u 字符指向的下一个结点，或着说是结点 p 代表的字符串后面添加一个字符 u 形成的字符串的结点。（u 的取值范围和字符集大小有关，不一定是 26，但本题都是小写字母，故取26）

有时需要标记插入进 Trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上cnt标记即可。

 

 

 

 1 #include <iostream>
 2 using namespace std;
 3 const int N = 20009;
 4 int trie[N][26],cnt[N];
 5 int idx;
 6 void insert(char str[])
 7 {
 8     int p = 0;
 9     for(int i = 0;str[i];++i)
10     {
11         int u = str[i] - 'a';
12         if(!trie[p][u])
13             trie[p][u] = ++idx;
14         p = trie[p][u];
15     }
16     ++cnt[p];
17 }
18 
19 int query(char str[])
20 {
21     int p = 0;
22     for(int i = 0;str[i];++i)
23     {
24         int u = str[i] - 'a';
25         if(!trie[p][u])
26             return 0;
27         p = trie[p][u];
28     }
29     return cnt[p];
30 }
31 int n;
32 char str[N];
33 int main()
34 {
35     cin >> n;
36     while(n--)
37     {
38         char op;
39         cin >> op >> str;
40         if(op == 'I')
41             insert(str);
42         else
43             cout << query(str) << endl;
44     }
45     return 0;
46 }

 

 

 

 

 

 

 

阿三大苏打