ToB企服应用市场:ToB评测及商务社交产业平台

标题: 洛谷P3879 [TJOI2010] 阅读理解（c嘎嘎） [打印本页]
作者: 罪恶克星    时间: 4 天前
标题: 洛谷P3879 [TJOI2010] 阅读理解（c嘎嘎）
题目链接：P3879 [TJOI2010] 阅读理解 - 洛谷 | 计算机科学教导新生态
题目难度：普及


解题心得：介绍两种方法，第一种还是简朴粗暴的STL，起首定义一个string映射到set的map来统计一个单词在哪几篇短文中出现过，最后读入查询的单词直接输出即可，第一种方法是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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4