题目链接：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<bits/stdc++.h>
using namespace std;	
#define _for(i,a,b) for(int i=(a); i<(b); i++)
#define _rep(i,a,b) for(int i=(a); i<=(b); i++)
typedef long long ll;
const int N = 5 * 1e5 + 10;
int son[N][26],idx;
bool b[N][1010];
char str[10010];
int n,l,m;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
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;
}

void insert(char * str,int x)
{
    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];  // 移动到子节点
    }
	b[p][x] = true;//在第x行出现了 
}

void check(char * str)
{   
	int p = 0,flag = 1;
	for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a'; 
        if (!son[p][u]) 
        {
        	flag = 0;
			break; 
		}
        p = son[p][u];  // 移动到子节点
    }
	if(flag)
	{
		for(int i=1; i<=n; i++)
		{
			if(b[p][i]) cout<<i<<" ";//输出在哪一句出现过 
		}
	}
	cout<<'\n';
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr),cout.tie(nullptr);
注意：关闭输入输出同步流后不能使用getchar可以改用cin.get(); 
     
    n = read();
    
    for(int i=1; i<=n; i++)
    {
        l = read();
    	for(int j = 1; j<=l; j++)
    	{
    		cin >> str;
    		insert(str,i);
		}
	}
	
	m = read();
	for(int i=1; i<=m; i++)
	{
		cin >> str;
		check(str);
	 } 
	 		
    return 0;
}