洛谷P3879 [TJOI2010] 阅读理解（c嘎嘎）
题目链接：P3879 [TJOI2010] 阅读理解 - 洛谷 | 计算机科学教育新生态
题目难度：普及
解题心得：介绍两种方法，第一种还是简单粗暴的STL，首先定义一个string映射到set的map来统计一个单词在哪几篇短文中出现过，最后读入查询的单词直接输出即可，第一种方法是tire字典树，之前学过（这道题也算是复习下），下面介绍下tire字典树。
- Tire字典树：
可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子1->2 - > 6 - > 11，
表示的就是字符串 aba。
trie 的结构非常好懂，我们用 
表示结点 
的 
字符指向的下一个结点，或着说是结点 
代表的字符串后面添加一个字符 
形成的字符串的结点。（
的取值范围和字符集大小有关，不一定是 
。）
有时需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。
插入操作：
void insert(char *str)
{int p = 0; // 从根节点开始for (int i = 0; str[i]; i++){int u = str[i] - 'a'; // 计算字符 'str[i]' 的索引if (!son[p][u]) // 如果当前节点没有对应字符的子节点，创建一个新节点son[p][u] = ++idx;p = son[p][u]; // 移动到子节点}cnt[p]++; // 增加节点 p 的计数，表示一个单词的结束
}
查询操作
int query(char *str)
{int p = 0; // 从根节点开始for (int i = 0; str[i]; i++){int u = str[i] - 'a'; // 计算字符 'str[i]' 的索引if (!son[p][u]) // 如果当前节点没有对应字符的子节点，字符串不存在return 0;p = son[p][u]; // 移动到子节点}return cnt[p]; // 返回节点 p 的计数，即字符串在 Trie 中出现的次数}下面奉上代码：
#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;
}