题面：
维护一个字符串集合，支持两种操作：
①I x向集合中插入一个字符串 x；
②Q x询问一个字符串在集合中出现了多少次。
共有 \(N\) 个操作，所有输入的字符串总长度不超过 \(105\) ，字符串仅包含小写英文字母。
Trie字典树[1]
//输入：
I dog
I dot
//此时的树为：
d
|
o
/ \
g t
[1] [1]
-
简单的说，就是每条分支存储不同的单词，叶子节点
cnt为该条分支上单词出现的次数。
两个不同单词的相同前缀走同一条路径，当遇到不同单词时，路径分离。
每个节点最多可以拥有26个子节点（\(a～z\)）。 -
son数组存储着目前节点的下一节点。
第一维为当前节点的标号；
第二维为下一节点的字母映射。 -
idx代表着每个节点的标号。
因为idx每出现一个新节点就自增一次，也就说明每个cnt[idx]都是唯一确定的。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
void insert(string str) {
int p = 0; //当前节点指针
for (int i = 0; str[i]; i++) {
int j = str[i] - 'a'; //字母映射为序号
if (!son[p][j]) //当前子节点不存在
son[p][j] = ++idx; //节点持续自增
p = son[p][j]; //更新指针
}
cnt[p]++; //统计以此节点结束的字符串个数
}
int query(string str) {
int p = 0;
for (int i = 0; str[i]; i++) {
int j = str[i] - 'a';
if (!son[p][j]) //若不存在该词语，返回0
return 0;
else
p = son[p][j]; //否则往下继续走
}
return cnt[p];
}
int main()
{
int t;
char op;
string str;
cin >> t;
while (t--) {
cin >> op >> str;
if (op == 'I') insert(str);
else cout << query(str) << endl;
}
}