Trie树 0pts求助 玄关
查看原帖
Trie树 0pts求助 玄关
519276
W_Sibo楼主2024/10/23 20:54
#include <bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,m,ch[N][30],tot=0;
vector<int> v[N];
string s;
void insert(string s,int i){
	int n=s.length()-1,now=0;
	for(int i=1;i<=n;i++){
		if(!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++tot;
		now=ch[now][s[i]-'a'];
	} 
	if(!v[now].empty()&&v[now][v[now].size()-1]==i) return;
	v[now].push_back(i);
}
void ask(string s){
	int n=s.length()-1,now=0;
	for(int i=1;i<=n;i++){
		if(!ch[now][s[i]-'a']) return;
		now=ch[now][s[i]-'a'];
	}
	if(!v[now].empty()){
		for(int i=0;i<v[now].size()-1;i++){
			cout<<v[now][i]<<' ';
		}
		cout<<v[now][v[now].size()-1];
	}
	cout<<'\n';
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int len;
		cin>>len;
		for(int j=1;j<=len;j++){
			cin>>s;
			s=' '+s;
			insert(s,i);
		}
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>s;
		s=' '+s;
		ask(s);	
	}
}
2024/10/23 20:54
加载中...