1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <cstdio>
#include <cstring>
#include <vector>
#define N 1005
#define M 10005
#define SZ 200005
int n,m;std::vector<int> ans[M];
namespace Trie {
int ch[SZ][26],idx=1;std::vector<int> id[SZ];
inline void insert(char s[],int x) {
int len=strlen(s),rt=1;
for(int i=0;i<len;++i) {
int val=s[i]-'a';
if(!ch[rt][val]) ch[rt][val]=++idx;
rt=ch[rt][val];
}
id[rt].push_back(x);
}
inline void query(char s[],int x) {
int len=strlen(s),rt=1;bool error=false;
for(int i=0;i<len;++i) {
int val=s[i]-'a';
if(!ch[rt][val]) {error=true;break;}
rt=ch[rt][val];
}
if(!error) for(int i=0,sz=id[rt].size();i<sz;++i) {
int idx=id[rt][i];
if(ans[idx].empty()||ans[idx][ans[idx].size()-1]!=x) ans[id[rt][i]].push_back(x);
}
}
}
char ss[N][10005],s[25];
int main() {
scanf("%d",&n);fgets(ss[0],5005,stdin);
for(int i=0;i<n;++i) fgets(ss[i],5005,stdin);
scanf("%d",&m);
for(int i=0;i<m;++i) {
scanf("%s",s);
Trie::insert(s,i);
}
for(int i=0;i<n;++i) {
char *ptr=ss[i];int offset=0;
int l;sscanf(ptr,"%d%n",&l,&offset);ptr+=offset;
while(l--) {
sscanf(ptr,"%s%n",s,&offset);ptr+=offset;
Trie::query(s,i+1);
}
}
for(int i=0;i<m;++i) {
int sz=ans[i].size();bool first=true;
for(int j=0;j<sz;++j) {
if(first) first=false;
else putchar(' ');
printf("%d",ans[i][j]);
}
putchar('\n');
}
return 0;
}
|