洛谷P3879 [TJOI2010] 阅读理解（c嘎嘎）

题目链接：P3879 [TJOI2010] 阅读理解 - 洛谷 | 计算机科学教导新生态
题目难度：普及

解题心得：介绍两种方法，第一种还是简朴粗暴的STL，起首定义一个string映射到set的map来统计一个单词在哪几篇短文中出现过，最后读入查询的单词直接输出即可，第一种方法是tire字典树，之前学过（这道题也算是复习下），下面介绍下tire字典树。

• Tire字典树：
  

可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子1->2 - > 6 - > 11，

 表现的就是字符串 aba。
trie 的布局非常好懂，我们用 

 表现结点 

 的 

 字符指向的下一个结点，或着说是结点 

 代表的字符串后面添加一个字符 

 形成的字符串的结点。（

 的取值范围和字符集大小有关，不一定是 

。）
偶然需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。

插入操纵：

1. void insert(char *str)
2. {
3.     int p = 0;  // 从根节点开始
4.     for (int i = 0; str[i]; i++)
5.     {
6.         int u = str[i] - 'a';  // 计算字符 'str[i]' 的索引
7.         if (!son[p][u])  // 如果当前节点没有对应字符的子节点，创建一个新节点
8.             son[p][u] = ++idx;
9.         p = son[p][u];  // 移动到子节点
10.     }
11.     cnt[p]++;  // 增加节点 p 的计数，表示一个单词的结束
12. }

复制代码

查询操纵

1. int query(char *str)
2. {
3.     int p = 0;  // 从根节点开始
4.     for (int i = 0; str[i]; i++)
5.     {
6.         int u = str[i] - 'a';  // 计算字符 'str[i]' 的索引
7.         if (!son[p][u])  // 如果当前节点没有对应字符的子节点，字符串不存在
8.             return 0;
9.         p = son[p][u];  // 移动到子节点
10.     }
11.     return cnt[p];  // 返回节点 p 的计数，即字符串在 Trie 中出现的次数
12.      
13. }

复制代码

下面奉上代码：

1. #include <cstdio>
2. #include <algorithm>
3. #include <cmath>
4. #include <cstring>
5. #include <iostream>
6. using namespace std;
7. char s[10010];
8. int nex[500010][26],n,cnt=0;
9. bool b[500010][1010];
10. inline int read()
11. {
12.     int k=0,f=1;char ch=getchar();
13.     while(ch<'0'||ch>'9')
14.         {
15.                 if(ch=='-')
16.                         f=-1;
17.                 ch=getchar();
18.         }
19.     while(ch>='0'&&ch<='9')
20.         {
21.                 k=k*10+ch-'0';
22.                 ch=getchar();
23.         }
24.     return k*f;
25. }
26. inline void insert(int x)
27. {
28.     scanf("%s",s+1);
29.         int l=strlen(s+1);
30.     int now=0;
31.     for(int i=1;i<=l;i++)
32.         {
33.         int p=s[i]-'a';
34.         if(!nex[now][p])         //如果$Trie$树中没有这个单词的前缀就进行编号
35.                         nex[now][p]=++cnt;   //上文中说到的编号
36.         now=nex[now][p];         //接着深入一层，更新现在的位置
37.     }
38.     b[now][x]=1;                 //这个单词在第x行出现了
39. }
40. inline void check()
41. {
42.     scanf("%s",s+1);
43.         int l=strlen(s+1);
44.     int now=0,flag=1;
45.     for(int i=1;i<=l;i++)
46.         {
47.         int p=s[i]-'a';
48.         if(!nex[now][p])         //如果在Trie树中没有当前的字符，就可以直接break掉了
49.                 {
50.                         flag=0;
51.                         break;
52.                 }
53.         now=nex[now][p];         //否则就更新位置
54.     }
55.     if(flag)
56.                 for(int i=1;i<=n;i++)    //题面上说按字典序输出
57.                         if(b[now][i])
58.                                 printf("%d ",i); //输出在哪些句子中出现过
59.     puts("");                    //相当于printf("\n");其实这个条件很容易看不到，一定要注意啊！！
60. }
61. int main()
62. {
63.     n=read();
64.     for(int i=1;i<=n;i++)
65.         {
66.         int x=read();
67.         for(int j=1;j<=x;j++)    //一个单词一个单词的插入Trie树里
68.                         insert(i);
69.     }
70.     int m=read();
71.     for(int i=1;i<=m;i++)
72.                 check();
73.     return 0;
74. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。