C++ Trie树模版 及模版题 || Trie字符串统计

Trie树：用来高效的存储和查找字符串集合的数据结构。

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 x
；
Q x 询问一个字符串在集合中出现了多少次。
共有 N
个操作，所有输入的字符串总长度不超过 105
，字符串仅包含小写英文字母。

输入格式
第一行包含整数 N
，表示操作数。

接下来 N
行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x
在集合中出现的次数。

每个结果占一行。

数据范围
1≤N≤2∗104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1
一些有助于理解的：
（1）关于理解int son[N][26] 这个二维数组的心得

Tire树本质上一个多叉树，最多可以分多少叉呢？因为此题存的都是小写字母，所以是26叉；

这里就解释了son这个二维数组的第二维的含义，就是他最多有26个孩子，那么他是谁呢，他当然是结点了，那结点之间怎么区分，或者这些孩子的爸爸叫啥，爸爸们用下标来区别，所以第一维就是爸爸们的id，son[0][1]含义就是0号爸爸有个儿子b ，那son[0][1] = 2，就是0号爸爸有个儿子b，儿子的id是2； 这些id就是由idx` 来赋值的；

idx可以理解为计划生育的管理局的给上户口的，生一个孩子，给孩子上身份证，证件上ID 为++idx ，而孩子叫啥，其实就是26个小写字母中的其中一个了；

对于每个结点而言，可以知道他有没有这个孩子，有的话叫啥，在哪里；

对于查询，从根节点一路查下来，就可以找到某个字符串在不在；

对于插入字符串，也是一路下来，看有没有这个儿子，没有了给你生个儿子，有了继续给下面找，所以只插入该字符串中原来不存在的字符即可； 也就是利用了公共前缀来降低查询时间的开销以达到提高效率的目的;

“Trie这个名字取自“retrieval”，检索，因为Trie可以只用一个前缀便可以在一部字典中找到想要的单词。”

（2）trie树那里，一开始以为[N][26]的第一维度是树的层数；其实，一维是结点总数，而结点和结点之间的关系（谁是谁儿子）存在第二个维度，比如[0][1]=3, [0]表示根节点，[1]表示它有一个儿子‘b’,这个儿子的下标是3；接着如果有一个[3][2]=8 ; 说明根节点的儿子‘b’也有一个儿子‘c’，这个孙子的下标就是8；这样传递下去，就是一个字符串。随便给一个结点][x][y], 并不能看出它在第几层，只能知道，它的儿子是谁。

#include <iostream>using namespace std;const int N = 100010;int son[N][26], cnt[N], idx; //下标是0的点，即是根节点又是空节点
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[0] == 'I') insert(str);else printf("%d\n", query(str));}return 0;
}