洛谷P3879 [TJOI2010] 阅读理解（c嘎嘎）
题目链接：P3879 阅读理解 - 洛谷 | 计算机科学教导新生态题目难度：普及
https://i-blog.csdnimg.cn/direct/223da6c7b5d74d498ec93de464fe83e8.png
解题心得：介绍两种方法，第一种还是简朴粗暴的STL，起首定义一个string映射到set的map来统计一个单词在哪几篇短文中出现过，最后读入查询的单词直接输出即可，第一种方法是tire字典树，之前学过（这道题也算是复习下），下面介绍下tire字典树。
[*]Tire字典树：
https://i-blog.csdnimg.cn/direct/8df3f4b82d8246d5ae0c61e8bdba66f8.png
可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子1->2 - > 6 - > 11，https://i-blog.csdnimg.cn/direct/8625e3e40fff4b8b9aa70c52fef7eb86.gif 表现的就是字符串 aba。
trie 的布局非常好懂，我们用 https://i-blog.csdnimg.cn/direct/5c2366fc18414899a8f5dedbdd35f034.gif 表现结点 https://i-blog.csdnimg.cn/direct/bbb8efce66cb413d994e972b60a27dc2.gif 的 https://i-blog.csdnimg.cn/direct/5cb06cade6c3440cbd17c10d486a7594.gif 字符指向的下一个结点，或着说是结点 https://i-blog.csdnimg.cn/direct/6f31d93510124ccbb2ce99deecdb8d1e.gif 代表的字符串后面添加一个字符 https://i-blog.csdnimg.cn/direct/86c33039eeca44e9be6f9dc2c6be4045.gif 形成的字符串的结点。（https://i-blog.csdnimg.cn/direct/9e8da955b9934f819618e9b69387ab2a.gif 的取值范围和字符集大小有关，不一定是 https://i-blog.csdnimg.cn/direct/ef92cb63ff28482a886a413adc9af6bc.gif。）
偶然需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。
插入操纵：
void insert(char *str)
{
int p = 0;// 从根节点开始
for (int i = 0; str; i++)
{
int u = str - 'a';// 计算字符 'str' 的索引
if (!son)// 如果当前节点没有对应字符的子节点，创建一个新节点
son = ++idx;
p = son;// 移动到子节点
}
cnt++;// 增加节点 p 的计数，表示一个单词的结束
}
查询操纵
int query(char *str)
{
int p = 0;// 从根节点开始
for (int i = 0; str; i++)
{
int u = str - 'a';// 计算字符 'str' 的索引
if (!son)// 如果当前节点没有对应字符的子节点，字符串不存在
return 0;
p = son;// 移动到子节点
}
return cnt;// 返回节点 p 的计数，即字符串在 Trie 中出现的次数
}
下面奉上代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
char s;
int nex,n,cnt=0;
bool b;
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-'a';
if(!nex) //如果$Trie$树中没有这个单词的前缀就进行编号
nex=++cnt; //上文中说到的编号
now=nex; //接着深入一层，更新现在的位置
}
b=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-'a';
if(!nex) //如果在Trie树中没有当前的字符，就可以直接break掉了
{
flag=0;
break;
}
now=nex; //否则就更新位置
}
if(flag)
for(int i=1;i<=n;i++) //题面上说按字典序输出
if(b)
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;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]