试图和大家一起理解y总的Trie模板。

基本的题目信息就不说了，这里需要知道一点点用数组模拟树的知识。

y总模板

#include <iostream>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
char str[N];

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];
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/45282/
来源：AcWing

本咸鱼稍微改写了一下下，用了string，起了新的变量名，方便理解

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5+10; 
int son[N][26],idx; 
int cnt[N]; 

void insert(string s){
    int next_pos = 0; //下一个要插入的层
    for(int i = 0; i < s.size(); i ++)
    {
        int bias = s[i] - 'a'; //计算下标；
        if(son[next_pos][bias] == 0) son[next_pos][bias] = ++idx;
        next_pos = son[next_pos][bias];
    }
    cnt[next_pos] ++;
}

int query(string s){
    int next_pos = 0;
    for(int i = 0; i < s.size(); i ++)
    {
        int bias = s[i] - 'a';
        if(son[next_pos][bias] == 0) return 0;
        next_pos = son[next_pos][bias];
    }
    return cnt[next_pos];
}
int main(){
    int num;
    cin >> num;
    while(num --){
        string a,b;
        cin >> a >> b;
        if(a == "I") insert(b);
        if(a == "Q") cout << query(b) << endl;
    }
    return 0;
}

接下来分段解释一下

全局变量部分

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5+10; 
int son[N][26],idx; 
int cnt[N]; 

这个idx是什么呢，是新需要插入的节点的编号，我们知道trie高效的原因之一是储存了公共的前缀，所以这些前缀节点再次插入的时候，是不需要另外储存的，idx只是需要新储存的节点编号。

那么这个son矩阵是干嘛的呢？这就是y总模板厉害的地方了，son这个矩阵有多个用处。

如果son[i]这一行由元素不为0，那么它表示的是某个字母，至于是哪个字母下一段代码再分解。它储存的值，是下一个新插入元素的位置。注意如果要插入停止符，也会单独占用一个idx。

cnt是什么呢，是对应每个停止符的数量。

insert函数

void insert(string s){
    int next_pos = 0; //下一个要插入的层
    for(int i = 0; i < s.size(); i ++)
    {
        int bias = s[i] - 'a'; //计算下标；
        if(son[next_pos][bias] == 0) son[next_pos][bias] = ++idx; //如果这个字符是需要新插入的，那么就往这个位置[next_pos][bias]插入
        next_pos = son[next_pos][bias];
    }
    cnt[next_pos] ++;
}

稍微给换了个名字以及用了STL string库。
next_pos指的是下个要插入的层的位置（层指的是son矩阵的第一个坐标），如果是需要新插入的字符，那么就在这层插入，这层什么位置插入呢？在字符本身-‘a’的地方插入，那么插入什么呢？插入的值是下一个新插入字符预定的层的位置，也就是idx+1，合并到一起写就是++idx了（这里可以把son的每一层看作是一个数组模拟的树）。无论是否新插入了字符，这个时候son[next_pos][bias]储存的都是下一个需要（新插入字符）的位置，所以就把next_pos更新一下好了。最后是如果没东西了，就是插入终止符，由于字符串是按照顺序插入的，所以每个字符串有自己独特的停止符位置，就利用这个计数。

query函数

int query(string s){
    int next_pos = 0;
    for(int i = 0; i < s.size(); i ++)
    {
        int bias = s[i] - 'a';
        if(son[next_pos][bias] == 0) return 0;
        next_pos = son[next_pos][bias];
    }
    return cnt[next_pos];
}

query函数比insert好理解很多，就是找到特定string对应的终止符的位置，然后读取数量就可以了。

大概就是这样。。。
希望可以和大家一起理解学习y总代码。