目录
🍔Trie树🍔
用处：高效地存储字符串集合的数据结构
概述：就是一个树状结构的存储方式，使用二维数组来存储，其中包含了父结点和子结点，从上向下开始遍历，看是否能够找到对应的结点，从而判断能否找到对应的字符串
存储方法（注意标记结束结点）
图像来源：AcWing 835. Trie字符串统计 - AcWing
下面的结点都是新开辟的结点，u代表字母，来确定结点的具体位置
不知道为什么，这个题在y总的课里面是基础算法，但是在洛谷上却是普及+的
那么下面就先给出两道简单的（可以作为模板使用）
回归正题
题目1
代码
#include<bits/stdc++.h> using namespace std; const int N=10010; int son[N][26],cnt[N],idx; void insert(string s) { int p=0; for(int i=0;i<s.size();i++) { int u=s[i]-'A'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cnt[p]++; } int main() { string s; while(cin>>s) { insert(s); } cout<<idx+1<<endl; return 0; }
⭐while(cin>>s)
边输入边循环，直到输入到结束符EOF为止
题目2
代码
#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)//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);//op[0] else printf("%d\n", query(str)); } return 0; }
🍔🍔🍔代码分析
⭐代码里面的int son[N][26],不能写成int son[N][N],
因为N就很大了，如果写成son[N][N],相当于存储的是N * N，会爆int
⭐int son[N][26];
son[][]存储子节点的位置，因为有26个字母，所以分支最多26条
⭐ int u = str[i] - 'a';
用来记录每个字母的位置是什么
⭐insert（）
if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u];
如果不存在这个结点不存在它的儿子的话，就创建一个结点，它的值为下一个结点的位置上的值
否则 使 p 指针指向下一个位置
相当于：有路的话，就走下去（idx++），否则建一条路也要走下去（p）
query（）
if (!son[p][u]) return 0; p = son[p][u];
如果不存在这个结点的话，就是没有查询到，就要返回0（return 0）
否则 使 p 指针指向下一个位置
⭐cnt[]存储以某节点结尾的字符串个数（同时也起标记作用）
cnt[p]++:表示以这个结点结尾的字符串的个数+1
return cnt[p]; 返回字符串出现的次数
⭐++idx
当前插入的结点是哪一个，加入新的结点就用++idx分配出一个下标
Code over!
