网站建设详细描述产品的是什么意思,品牌营销策划培训课程,职业生涯规划ppt免费模板,vi设计网站运动康复Trie树#xff1a;用来高效的存储和查找字符串集合的数据结构。
维护一个字符串集合#xff0c;支持两种操作#xff1a;
I x 向集合中插入一个字符串 x #xff1b; Q x 询问一个字符串在集合中出现了多少次。 共有 N 个操作#xff0c;所有输入的字符串总长度不超过 1…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个孩子那么他是谁呢他当然是结点了那结点之间怎么区分或者这些孩子的爸爸叫啥爸爸们用下标来区别所以第一维就是爸爸们的idson[0][1]含义就是0号爸爸有个儿子b 那son[0][1] 2就是0号爸爸有个儿子b儿子的id是2 这些id就是由idx 来赋值的
idx可以理解为计划生育的管理局的给上户口的生一个孩子给孩子上身份证证件上ID 为idx 而孩子叫啥其实就是26个小写字母中的其中一个了
对于每个结点而言可以知道他有没有这个孩子有的话叫啥在哪里
对于查询从根节点一路查下来就可以找到某个字符串在不在
对于插入字符串也是一路下来看有没有这个儿子没有了给你生个儿子有了继续给下面找所以只插入该字符串中原来不存在的字符即可 也就是利用了公共前缀来降低查询时间的开销以达到提高效率的目的;
“Trie这个名字取自“retrieval”检索因为Trie可以只用一个前缀便可以在一部字典中找到想要的单词。”
2trie树那里一开始以为[N][26]的第一维度是树的层数其实一维是结点总数而结点和结点之间的关系谁是谁儿子存在第二个维度比如[0][1]3, [0]表示根节点[1]表示它有一个儿子‘b’,这个儿子的下标是3接着如果有一个[3][2]8 ; 说明根节点的儿子‘b’也有一个儿子‘c’这个孙子的下标就是8这样传递下去就是一个字符串。随便给一个结点][x][y], 并不能看出它在第几层只能知道它的儿子是谁。
#include iostreamusing 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;
}
