[TJOI2010] 阅读理解

洛谷

题意：给定\(N\)篇短文，每篇短文由\(L\)个单词组成，且只含小写字母；做\(M\)次询问，每次给定一个单词，求该单词在哪几篇短文中出现过。对于 \(100\%\) 的数据，\(1\le M\le 10^4\)，\(1\le N\le 10^3\) 。每篇短文长度（含相邻单词之间的空格）\(\le 5\times 10^3\) 字符，每个单词长度 \(\le 20\) 字符。

分析：接近于Trie字典树的模板题，建树的时候对于每个单词的尾节点，开一个\(vector\)数组记录属于哪些文章，注意可能同一篇短文出现同一个单词多次，这时只要插入一次短文的编号。查询的时候直接输出单词尾节点的\(vector\)数组内容即可。本题最奇怪的点在于数组大小，表面上最多可能会有\(5e6\)个字符，而且每个字符都要有一个26个小写字母的指针域，但是这样建肯定会\(MLE\)，实际上肯定会有相同的字符共用一个节点，因此达不到\(5e6\)，建\(1e6\)就好了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e6+5;
const int M=3e5+5;
const int mod=998244353; 
int tot,ch[N][30];
vector<int>q[N];
void insert(string s,int num){
    int u=0;
    int len=s.size();
    for(int i=0;i<len;i++){
		int c=s[i]-'a';
		if(!ch[u][c])ch[u][c]=++tot;
		u=ch[u][c];
    }
    if(q[u].empty()||q[u][q[u].size()-1]!=num)q[u].push_back(num);
    return;
}
void find(string s){
	int len=s.size();
    int u=0;
    for(int i=0;i<len;i++){
    	int c=s[i]-'a';
        if(!ch[u][c]){
        	cout<<endl;
        	return;
		}
        u=ch[u][c];
    }
    for(int i=0;i<q[u].size();++i)cout<<q[u][i]<<" ";
	cout<<endl;
	return;
}
int main(){
    int n=read();
	for(int i=1;i<=n;++i){
		int L=read();
		for(int j=1;j<=L;++j){
			string s;
			cin>>s;
			insert(s,i);
		}
	}
	int m=read();
	for(int i=1;i<=m;++i){
		string s;
		cin>>s;
		find(s);
	}
    return 0;
}