做网站费用怎么入账,中美关系最新消息新闻,网线制作方法,大连网站建设仟亿科技1、“Trie树” 作用#xff1a;
高效地存储和查找字符串集合的数据结构。
2、“Trie树” 存储字符串的形式如下#xff1a; 用 “0” 来表示 “根节点#xff08;root#xff09;”。存入一个字符串时#xff0c;会在字符串最后结尾的那个字符节点打上标记。比如#x…1、“Trie树” 作用
高效地存储和查找字符串集合的数据结构。
2、“Trie树” 存储字符串的形式如下 用 “0” 来表示 “根节点root”。存入一个字符串时会在字符串最后结尾的那个字符节点打上标记。比如字符串 “abcd” 是以字符 “d” 结尾的那么就在字符节点 “d” 打上标记。 具体例子理解
左边数组初始全是0 添加字符串”abc“
首先p 0 p 指的是当前所遍历到的节点 index 指的是最后一个可用的节点依次获取每个字符(首先获取字符a)映射的数字(0~25) 由于当前节点并没有a这个节点指向的节点 我们就需要新建一个节点然后我们把 idx 填写到这个节点上第一次是1 AcWing 835. Trie字符串统计
#include iostreamusing 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[])
{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;
}