这是这题我第三次写题解惹555

$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：
Trie是一棵树，有很多节点（是人都知道），每两个节点的边都代表一个字符。

insert

也就是说，例如一个字符串abc
如果进行插入的话，那么，节点编号为0的节点，通过字符a到达节点编号为1的节点；节点编号为1的节点，通过字符b到达节点编号为2的节点；节点编号为3的节点，通过字符c到达节点编号为4的节点。最后，在节点4打上一个标记，也就是说节点4是其中一个字符串的结束位置
在这道题中，要求的是字符串出现的次数，所以不能简单地用标记数组进行01标记，要存下这个节点是多少个字符串的结束位置。
到此，insert，插入一个字符串的函数就结束了。

query

插入完了，题目还有询问的部分尚未解决
如何询问呢？
其实和插入的思想很像，就是沿着线路进行搜索而已。
当到达某个节点i的时候，如果下一个字符是c，那么就看一下i通过c能到达哪一个节点。如果该节点为空，那么就直接返回$0$。否则如果遍历完这个要查询的字符串，那么就返回最后这个节点的权值（出现次数）。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx; //下标是0的点，既是根节点，又是空节点
string str;
void insert(string 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(string 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() {
    int n; cin>>n;
    while (n--) {
        string op; cin>>op>>str;
        if (op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }
}