本人看了y总多遍视频后略懂 写一篇题解来巩固下自己的对 Trie字符串 的认识

(PS：本人少写题解 如有误区请指正 大佬勿喷蟹蟹)

原题链接 ：

https://www.acwing.com/problem/content/837/

1. p 是什么？

答：p 是根节点

2. idx 是什么？

答：idx 是每一个节点的编号 每一个新节点(指不重复 新创建的节点)都会有个独一无二的编号

3. son[p][u] 又是什么？

答：son[p][u] 的值为下一个节点的编号， p 为当前节点的编号，u 为当前字母(可用 u + ‘a’ 根据 asc 码值推断出) p 和 u 的共同存在可以确定一个节点的具体位置

p 为根节点我们可以从 y 总视频中知晓 同时我们在视频中不难发现 p不管是在插入(insert)还是访问寻找(query)都是以 p = 0 开始 即我们每次去插入一个字符串我们需要从数组的第一维找是否有其字符串第一个字母的存在 这也是 son 数组创建为 son[N][26]的原因 因为每个节点最多存在 26 条路径（有且仅有 26 种字母的选择）

插入操作中每次 son[p][u] == 0 (即不存在时) 就 ++ idx (即让 idx 指向有下一个新节点) 且插入操作和询问操作代码中有这么一行代码 p = son[p][u] 也就是为了让下一节点的值为 son[p][u]; 这里有一个要点就是当前一个字符串结束后 字符串最后一个字母对应的节点 idx1 的下一个节点 idx2 也会被创立 并且让
cnt[idx2] ++;

上图直观点 （字丑见谅）橙色部分为新创立的节点

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int s[N][26], cnt[N], idx = 0;

void insert(char str[])// 插入字符串
{
    int p = 0;// 当前节点位置
    for(int i = 0; str[i] != '\0'; i ++ ){
        int u = str[i] - 'a';// 将字母转换为数字
        if(s[p][u] == 0) s[p][u] = ++ idx;// 如果当前节点不存在就创建一个节点 节点的值指向下一节点
        p = s[p][u];// p 每次更新为下一节点的值
    }
    cnt[p] ++;// 字符串结尾最后一个字母节点的下个节点做上标记
}

int query(char str[])// 查询操作
{
    int p = 0;
    for(int i = 0; str[i] != '\0'; i ++ ){
        int u = str[i] - 'a';
        if(s[p][u] == 0) return 0;// 如果字符串在当前节点不存在 那说明不存在此字符串直接退出
        p = s[p][u];// 否则继续向下走 直至读到 '\0'
    }
    return cnt[p];// 退出循环则说明找到完整的 str 字符串，返回 str 字符串出现的次数即可
}

int main()
{
    int t;
    cin >> t;
    while( t -- ){
        char ch, str[N] = {0};
        cin >> ch >> str;
        if(ch == 'I'){
            insert(str);
        }else {
            cout << query(str) << endl;
        }
    }
}