题解 P3879 【[TJOI2010]阅读理解】
Hatsune_Miku
2018-05-27 15:41:10
据说本题是一个 ``普及/提高-`` 的题目？蒟蒻我表示很震惊啊。这明明是Trie树的板子题啊~~（好像Trie树全都是模板题）~~。
其实这道题目是我旁边一位dalao推荐我做的，又因为好久不写数据结构题了，然后就选择了这么一道水题来写。
其实感觉Trie树没有什么好说的，大体思路就是直接模拟一下，把字符串的每一个字符丢到一棵树上，然后查找就是遍历一遍这棵树。一般情况下字符串匹配问题在空间不是非常紧张的情况下都是可以使用Trie进行快速的匹配的。当然Trie树还有更多奇奇怪怪的用途~~（可以出各种各样奇奇怪怪的题目）~~。
主要操作大概就是一个插入和查找的操作。可以参考dalao的题解学习。要通过这道题仅仅需要在Trie的每个节点上添加一个 ``vector<int>`` 记录一下每个单词在哪些句子中出现过就行了~~（可能是指针党的福利？）~~。
附上不清真的指针版Trie树代码：
```cpp
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
namespace trie{
struct node{
node *nxt[26];
bool isStr;
vector<int>v;
node(){
memset(nxt,0,sizeof nxt);
v.clear();
}
};
inline void insert(node *root,char *str,int cnt){
if(!root||!*str)return;
while(*str){
int p=*str-'a';
if(!root->nxt[p])root->nxt[p]=new node();
root=root->nxt[p];
++str;
}
if(!root->v.size()||*(root->v.end()-1)!=cnt)root->v.push_back(cnt);
}
inline void find(node *root,char *str){
if(!root||!*str)return;
while(*str){
int p=*str-'a';
if(!root->nxt[p])return;
root=root->nxt[p];
++str;
}
for(vector<int>::iterator it=root->v.begin();it!=root->v.end();++it)
printf("%d ",*it);
}
}
using namespace trie;
char s[25];
int n,m,l;
int main(){
node *root=new node();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&l);
while(l--){
scanf("%s",s);
insert(root,s,i);
}
}
scanf("%d",&m);
while(m--){
scanf("%s",s);
find(root,s);
puts("");
}
return 0;
}
```
~~（不要吐槽代码风格了）~~