阅读理解

 1 题目描述
 2 英语老师留了N篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。
 3 输入格式
 4 第一行为整数N，表示短文篇数，其中每篇短文只含空格和小写字母。
 5 按下来的N行，每行描述一篇短文。每行的开头是一个整数L，表示这篇短文由L个单词组成。接下来是L个单词，单词之间用一个空格分隔。
 6 然后为一个整数M，表示要做几次询问。后面有M行，每行表示一个要统计的生词。
 7 输出格式
 8 对于每个生词输出一行，统计其在哪几篇短文中出现过，并按从小到大输出短文的序号，序号不应有重复，序号之间用一个空格隔开（注意第一个序号的前面和最后一个序号的后面不应有空格）。如果该单词一直没出现过，则输出一个空行。
 9 输入输出样例
10 输入 #1 
11 3
12 9 you are a good boy ha ha o yeah
13 13 o my god you like bleach naruto one piece and so do i
14 11 but i do not think you will get all the points
15 5
16 you
17 i
18 o
19 all
20 naruto
21 输出 #1 
22 1 2 3
23 2 3
24 1 2
25 3
26 2
27 说明/提示
28 对于30%的数据，1 ≤ M ≤ 1,000
29 对于100%的数据，1 ≤ M ≤ 10,000，1 ≤ N ≤ 1000
30 每篇短文长度（含相邻单词之间的空格） ≤ 5,000 字符，每个单词长度 ≤ 20 字符
31 每个测试点时限2秒

阅读理解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char s[30000];
 4 int nw,len,n,l,m,tot,fg;
 5 bitset<1020> b[500020];
 6 int t[500002][30];
 7 void insert(int x)
 8 {
 9     len=strlen(s+1);nw=0;
10     for(int i=1,k;i<=len;++i)
11     {
12         k=s[i]-'a';
13         if(!t[nw][k]) t[nw][k]=++tot;
14         nw=t[nw][k];
15     }
16     b[nw][x]=1;
17 }
18 void find()
19 {
20     fg=0;
21     len=strlen(s+1);nw=0;
22     for(int i=1,k;i<=len;++i)
23     {
24         k=s[i]-'a';
25         if(!t[nw][k]){fg=1;break;}
26         nw=t[nw][k];
27     }
28     if(fg);
29     else{
30         for(int i=1;i<=n;++i)
31          if(b[nw][i]) printf("%d ",i);
32     }
33     printf("
");
34 }
35 int main()
36 {
37     scanf("%d",&n);
38     for(int i=1;i<=n;++i)
39     {
40         scanf("%d",&l);
41         for(int j=1;j<=l;++j) 
42         {
43             scanf("%s",s+1);
44             insert(i);
45         }
46     }
47     scanf("%d",&m);
48     for(int i=1;i<=m;++i) 
49     {
50         scanf("%s",s+1);
51         find();
52     }
53     return 0;
54 }

View Code