做图赚钱的网站有哪些,网站加搜索框,网站百度推广怎么做,北京专业网站设计报价概念#xff1a;
Trie 是一种能够快速插入和查询字符串的多叉树结构。、
节点的编号各不相同#xff0c;根节点编号为0#xff0c;其他节点用来标识路径#xff0c;还可以标记单词的插入次数#xff0c;边表示字符。 tire 维护字符串的集合#xff0c;支持两种操作
Trie 是一种能够快速插入和查询字符串的多叉树结构。、
节点的编号各不相同根节点编号为0其他节点用来标识路径还可以标记单词的插入次数边表示字符。 tire 维护字符串的集合支持两种操作
1. 向集合中插入一个字符串
2. 在集合中查询一个字符串
建字典树
儿子数组 son[p][26] : 存储从节点p沿着j这条边走到的子节点。边为26个小写字母a~z)对应的映射值0~25每个节点最多可以有26个分叉。
计数数组 cnt[p] : 存储以节点p结尾的单词的插入次数
节点编号 idx : 用来给节点编号 1. 空 trie 仅有一个根节点编号为0
2. 从根开始插枚举字符串的每个字符 如果有儿子则p指针走到儿子 如果没有儿子则 先创建儿子p指针再走到儿子
3. 在单词结束点记录插入次数 模板
int son[N][26], cnt[N], idx;
// 0号点既是根节点又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
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];
}
例题835. Trie字符串统计 - AcWing题库
题目
维护一个字符串集合支持两种操作
I x 向集合中插入一个字符串 xQ x 询问一个字符串在集合中出现了多少次。
共有 N 个操作所有输入的字符串总长度不超过 105105字符串仅包含小写英文字母。
输入格式
第一行包含整数 N表示操作数。
接下来 N 行每行包含一个操作指令指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x都要输出一个整数作为结果表示 x 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗10^4
输入样例
5
I abc
Q abc
Q ab
I ab
Q ab输出样例
1
0
1代码
#includeiostream
#includealgorithm
#includecmath
#includecstdio
#includestring
#includequeue
#includecstring
#includesstream
#includestring.h
#includevectorconst int N 1e5 10;
using namespace std;
typedef pairint ,int PII;
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;cin 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;
}
