目录

                                                代码 

---

（一）输入cat

son[p][u],p表示儿子，u表示第几个儿子

0的根的节点编号为idx

--------------------------------------------------------

根是0的有个儿子c，编号为1的节点有个子节点为a，a的编号是2，a相当于父节点。

2的子节点为编号3（t）

3的子节点没有了。cnt++

 （二）在输入cash，p从1开始，idx还是3

son用来交换的

c有，son也重新来=1，p=1

a也有，son=2，p=2

a下找s有没有，没，idx变为4

                                                代码 

写入每一格编号

#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';                                 //u成为行，if(!son[p][u]) son[p][u]=++idx;//!son[p][u]为son不等于零，就idx全局++,返回增值后的值p=son[p][u];//2对应的新加的字母u有没有，没有给p    //p=son[p][u]儿子变成父亲}cnt[p]++;                                             //是一个单词，cnt统计字符串数量
}
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];printf("%d%d%d",cnt[p],str[i],idx);}return cnt[p];                      //统计字符串数量
}
int main(){int m;cin>>m;while(m--){char op[2];scanf("%s%s",op,str);if(*op== 'I') insert(str);else printf("%d\n", query(str));}    return 0;
}
//注：I就不返回，Q才有返回值
//注：op命令，str插入的// 5
// I abc
// Q abc
// 1
//  Q ab
// 0
//  I ab
// Q ab
// 1

1. son[p][u] 表示在Trie树中节点 p 的第 u 个儿子，其中 u 的范围是 0 到 25，对应于小写字母表中的每个字母。
2. cnt[p] 表示以 son[p] 结尾的字符串的数量。
3. insert(char *str)如果当前字符在 son[p] 中不存在，则创建一个新的节点，并将其添加到 son[p] 中。然后，将当前节点更新为新创建的节点，并将以新节点结尾的字符串数量加一。
4. query(char *str)如果存在，则将当前节点更新为该儿子节点，并返回以该节点结尾的字符串的数量。