# 1 字典树的概念
字典树, 是一种树形结构, 是一种哈希树的变种.(来自度娘百科)
首先, 字典树的每一个节点都是长这样的:
- struct node{
- int end,son[27];
- }a[maxn]
每个节点都有一个判断自己是多少个单词结尾的 end 与它之后的节点 son[27].
# 2 如何构造字典树
假设我们输入:
- 7
- b
- ab
- ba
- bb
- aab
- baa
- aba
我们会得到一个这样的结果:
我们可以轻松地找出每个节点的 end 值, 如下:
这样, 我们就成功构建了一棵字典树!
# 3 例题
例题 阅读理解 https://www.luogu.org/problemnew/show/P3879
分析:
step1: 我们将每一篇文章中的每一个单词, 用字典树的方式存储, 记得标上自己是属于哪一篇文章的.
step2: 对于每一个需要查询的单词, 从根节点开始, 不断向下遍历, 如果在单词的结尾刚好有一篇文章的一个单词结尾在这里, 输出文章号就 OK 了.
代码 (很久以前的代码, 码风还 OK, 不过没有用上文的方式存储):
- #include<bits/stdc++.h>
- using namespace std;
- int n,q,t,sum,son[500005][27];
- bitset<1005> ans[500005];
- map<string,int>m;
- string str;
- void change(int x,string s){
- int tmp=0;
- for(int j=0;j<s.size();tmp=son[tmp][s[j++]-96])
- if(son[tmp][s[j]-96]==0)
- son[tmp][s[j]-96]=++sum;
- m[s]=tmp;
- ans[tmp][x]=true;
- }
- void query(string s){
- if(m.count(s)){
- int num=m[s];
- for(int j=1;j<=n;++j)
- if(ans[num][j]==true)
- printf("%d",j);
- }
- puts("");
- }
- int main(){
- scanf("%d",&n);
- for(int i=1;i<=n;++i){
- scanf("%d",&t);
- for(int j=1;j<=t;++j){
- cin>>str;
- change(i,str);
- }
- }
- scanf("%d",&q);
- for(int i=1;i<=q;++i){
- cin>>str;
- query(str);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2946506.html