Trie反复全RE,求大佬指点
查看原帖
Trie反复全RE,求大佬指点
631544
li_cat楼主2024/4/13 23:34
#include <bits/stdc++.h>
#define MAXN 5005
#define MAXM 1010
#define str string
#define end ending
using namespace std;
int n,l,m;
int hash_(char ch){
	return int(ch-'a');
}
int edge[MAXN][27],cnt;
bool end[MAXN][MAXM];
void first(){
	for(int i=1;i<=cnt;++i){
		for(int j=0;j<n;++j) end[i][j]=false;
		for(int j=0;j<=26;++j) edge[i][j]=0;
	}
	cnt=1;
}
void add(str s,int sh){
	int p=1,i=0,len=s.size();
	while(i<len){
		int h=hash_(s[i]);
		if(!edge[p][h]) edge[p][h]=++cnt;
		p=edge[p][h];
		++i;
	}
	end[p][sh]=true;
}
void in(str s){
	int p=1,i=0,len=s.size();
	while(i<len){
		int h=hash_(s[i]);
		if(!edge[p][h]){
			cout<<endl;return ;
		}
		p=edge[p][h];
		++i;
	}
	for(int j=1;j<=n;++j) if(end[p][j]) cout<<j<<' ';
	cout<<endl;
}
int main(){
	cin>>n;
	first();
	for(int i=1;i<=n;++i){
		cin>>l;
		for(int j=1;j<=l;++j){
			str s;cin>>s;
			add(s,i);
		}
	}
	cin>>m;
	for(int i=0;i<m;++i){
		str s;
		cin>>s;
		in(s);
	}
	return 0;
}
2024/4/13 23:34
加载中...