题解 P3879 【[TJOI2010]阅读理解】
Ervin
·
·
题解
这道题看一眼就知道这是个STL库里的map
- 但是。。
神犇我选择了Trie树，Hahahaha...- 可能没有dalao发这个题目的Trie树题解是因为太麻烦了、、、不过A+B Problen都有发各种
看不懂的题解的人，我发个Trie树也没有什么说不过去的吧、、
******* dalao 专用分割线******
可能有的小朋友们还不知道Trie树是什么(虽然我也是刚刚才知道)，我还是先讲一下Trie树吧。。
那什么时候会用到$Trie$树呢？
举个例子吧：
1. 就像这道题目一样，查寻这个单词在一句话中出现还是没有出现，非常简单么，$map$啊，~~短小精干~~
2. 但是，如果给出$n$个单词和$m$组询问，询问是多少个单词的前缀，那么$map$的话就完美的$TLE$了，这个时候就要使用久违的$Trie$树了！！
$Second$，先模拟一下$Trie$树的各种操作吧。
如果要插入
$CAI,CHANG,CHAO,CHEN,LAN,LI,LIU,LONG,
所建出的$Trie$树就是这样的。
## 呈上图来：
### 注意：$Trie$树的根节点是空的，然后在单词的末尾有个标记，这点事必不可少的。
$Then$，介绍一下$Trie$树的基本操作吧。
$A.$ $Insert$插入：
1. 首先要给所有的字母一个编号，其实并不用从$a...z$全部都编号，你会发现其实有很多字母是用不到的，所以只需要判断树中有没有这个单词的前缀，然后进行编号。
2. 编号完成后更新当前位置，接着进入下一个层。
#### 代码统一在后边统一粘上
$B.$ $Check$查询：
从$Trie$树的根开始，看有没有当前的字符，如果没有，就直接$break$掉，否则就跟新当前位置，进入下一层。
其实$Trie$树的常用操作就这两个，其实$Trie$树涉及的题目也不算很多，其实学习$Trie$树还可以为以后的$AC$自动机(~~就是用了这个算法就可以自动AC了~~)做一下铺垫。
----
----
好了，对于$Trie$树的介绍就到这里吧，下面就说这个题目了，其实这个题目就是一道裸裸的$Trie$树模板，写出上边介绍的两个操作，再加上点~~高深~~的东西就可以$AC$了。
下边直接粘代码吧：
```cpp
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
char s[10010];
int nex[500010][26],n,cnt=0;
bool b[500010][1010];
inline int read()
{
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
k=k*10+ch-'0';
ch=getchar();
}
return k*f;
}
inline void insert(int x)
{
scanf("%s",s+1);
int l=strlen(s+1);
int now=0;
for(int i=1;i<=l;i++)
{
int p=s[i]-'a';
if(!nex[now][p]) //如果$Trie$树中没有这个单词的前缀就进行编号
nex[now][p]=++cnt; //上文中说到的编号
now=nex[now][p]; //接着深入一层，更新现在的位置
}
b[now][x]=1; //这个单词在第x行出现了
}
inline void check()
{
scanf("%s",s+1);
int l=strlen(s+1);
int now=0,flag=1;
for(int i=1;i<=l;i++)
{
int p=s[i]-'a';
if(!nex[now][p]) //如果在Trie树中没有当前的字符，就可以直接break掉了
{
flag=0;
break;
}
now=nex[now][p]; //否则就更新位置
}
if(flag)
for(int i=1;i<=n;i++) //题面上说按字典序输出
if(b[now][i])
printf("%d ",i); //输出在哪些句子中出现过
puts(""); //相当于printf("\n");其实这个条件很容易看不到，一定要注意啊！！
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
int x=read();
for(int j=1;j<=x;j++) //一个单词一个单词的插入Trie树里
insert(i);
}
int m=read();
for(int i=1;i<=m;i++)
check();
return 0;
}
```
## 感谢大家的观看，上方点赞哦!!