题目链接 ：
点击查看
题目描述 ：
维护一个字符串集合，支持两种操作：
-
I x
向集合中插入一个字符串 x； -
Q x
询问一个字符串在集合中出现了多少次。
共有 N 个操作，输入的字符串总长度不超过 10^5 ，字符串仅包含小写英文字母。
输入输出格式：
输入
第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为
I x
或
Q x
中的一种。
输出
对于每个询问指令
Q x
，都要输出一个整数作为结果，表示 x 在集合中出现的次数。每个结果占一行。
输入输出样例 ：
输入
5
I abc
Q abc
Q ab
I ab
Q ab
输出
1
0
1
题目分析 ：
本题要用到Trie前缀树进行求解。Trie顾名思义，是一种利用字符串前缀进行高效存储和查找字符串的一种树形结构，其每个节点存储的是字符串中的字符，其子节点有着相同的字符前缀，若要以当前节点为结尾的字符串存在，则要对此节点加上标识。对于本题来说，字符串仅包含小写字母，意味着每个节点最多有26个子节点。要构建Trie树,需要以下准备 ： 1. son[N][26] 此数组用来记录节点数为n的节点的子节点，第二维定义26个大小对应着不同26个字母，其值即为节点序数。 2. cnt[N] 意为以n节点为结尾的字符串的数量，n为节点序数 3 .cur 记录当前已经生成节点的个数 ，同时cur ++ 后即为下一个(要生成的)节点序数。具体构建方法为 ：首先定义一个int p = 0，模拟指向节点指针，作为son第一维的下标。 对于当前传入的字符串str[n]， 其中一个字符str[i], 用int u = str[i] – ‘a'(计算出字符序数)，充当son第二维的下标。此时son[p][u]即为p的子节点的节点序数，如果son[p][u]存在(有值)说明之前已经构建过该分枝，直接令p = son[p][u], 即p指针移动到子节点，如son[p][u]不存在，则需要创建一个新节点进行储存，代码实现为 son[p][u] = ++ cur，再令 p = son[p][u]，如此循环处理直到字符串到达末尾。若在循坏结束时,令cnt[p] ++ 表示以传入字符串最后一个字符为末尾的字符串的个数,也可当做与当前传入字符串相同的字符串一共有几个。上述是构建过程，查询过程要容易得多，对于要查询的字符串，我们从串首字符开始，依次判断son[p][u]是否有值即可，若有值，表明之前插入过此字符，p要移动到下一个节点，继续查找。若无值(==0)，则没有此字符串，返回0即可。详见如下代码。
代码 ：
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5 + 7;
int son[N][26], cnt[N], cur;//cur表示生成的节点个数 , cnt[N]记录以每个节点为终点字符串的个数
char str[N]; //存储要操作字符串
void insert(char *str) {
int p = 0;//p模拟指向节点的指针
for (int i = 0; str[i]; i ++ ) {
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ cur;//如不存在，则生成新的节点
p = son[p][u]; //p移动到当前节点位置
}
cnt[p] ++ ;//以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];//p向下移动，移动到下一个节点
}
return cnt[p];//返回单词个数
}
int main() {
int n;
scanf ("%d", &n);
while (n -- ) {
char op[2];//op定义为2个大小的字符数组 可以吸收回车
scanf("%s%s", op, str);
if (*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}—————————————————————————-
下面给出Trie树模板
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
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];
}