题意描述

英语老师留了$N$篇阅读理解作业,但是每篇英文短文都有很多生词需要查字典。

为了节约时间,现在需要你来做个统计,算一算某些生词都在哪几篇短文中出现过。


输入格式

第一行为整数$N$,表示短文篇数,其中每篇短文只含空格和小写字母。

按下来的$N$行,每行描述一篇短文。每行的开头是一个整数$L$,表示这篇短文由$L$个单词组成。接下来是$L$个单词,单词之间用一个空格分隔。

然后为一个整数$M$,表示要做$M$次询问。后面有$M$行,每行表示一个要统计的生词。


输出格式

输出$M$行,分别表示每个生词在哪几篇短文中出现过。并按从小到大输出短文的序号。序号之间用一个空格隔开

如果该单词一直没出现过,则仅输出一个空行即可。


Input & Output ‘s examples

Input ‘s eg

3
9 you are a good boy ha ha o yeah
13 o my god you like bleach naruto one piece and so do i
11 but i do not think you will get all the points
5
you
i
o
all
naruto

Output ‘s eg

1 2 3
2 3
1 2
3
2

数据范围和约定

对于$30\%$的数据,$1 ≤ M ≤ 10^3$

对于$100\%$的数据,$1 ≤ M ≤ 10^5,1 ≤ N ≤ 10^3$

每篇短文长度(含相邻单词之间的空格) $≤ 5,000$个字符,每个单词长度 $≤ 20$个字符


分析

又是一道Trie树的模板

对于每篇文章,我们把它的每一个单词插入Trie树之中,之后用bool数组$flag[rt][i]$表示$rt$在第$i$篇文章中是否出现过。

查询时从小到大遍历每一篇文章(即$flag$数组的第二维),如果被标记过,输出即可。

最后别忘了输出空行。


$Upd$:后来有个老鸽传了一组数据,在空间上卡掉了用来判断是否出现的$flag$数组。针对这种做法,我们可以将其开为bitset

这样的话,$flag$数组的空间大小就变成了原来的$\frac{1}{32}$,即可轻松通过本题。

以及,bitset使用之前需要添加#include<bitset>


Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<bitset>

#define ll long long
#define I inline
#define N 500001

using namespace std;

int n , m , k;
bitset<1001> flag[N];

namespace Trie{
struct Node{
int son[26];
}node[N];

int tot = 0;

void insert(int x , string s){
int len = s.length() , rt = 0;
for(int i = 0; i < len; i ++){
int c = s[i] - 'a';
if(!node[rt].son[c]){
node[rt].son[c] = ++ tot;
}
rt = node[rt].son[c];
}
flag[rt][x] = true;
}

void find(string s){
bool bj = true;
int len = s.length() , rt = 0;
for(int i = 0; i < len; i ++){
int c = s[i] - 'a';
if(!node[rt].son[c]){
bj = false;
break;
}
rt = node[rt].son[c];
}
if(bj == true){
for(int i = 1; i <= n; i ++){
if(flag[rt][i]){
cout << i << " ";
}
}
}
cout << "\n";
}

}

int main(){
string str;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> m;
for(int j = 1; j <= m; j ++){
cin >> str;
Trie :: insert(i , str);
}
}
cin >> k;
for(int i = 1; i <= k; i ++){
cin >> str;
Trie :: find(str);
}
return 0;
}

THE END