trie树全TLE求调
查看原帖
trie树全TLE求调
737532
fantangsong楼主2024/7/27 14:42
#include<bits/stdc++.h>
#define in inline
using namespace std;
const int NM=5e5+10,N=1010;
int n,m,l,tot=1,ch[NM][30];
char s[5010];
bitset<1001>exist[NM];
in int read()
{
	int f=1,x=0;char c=getchar();
	while('9'<c||c<'0'){
		if(c=='-')f=-f;c=getchar();
	}
	while('0'<=c&&c<='9')
		x=x*10+c-'0',c=getchar();
	return x*f;
}
in void insert(char *s,int num)
{
	int len=strlen(s),u=1,i,c;
	for(i=0;i<len;++i){
		c=s[i]-'a';
		if(!ch[u][c])ch[u][c]=++tot;
		u=ch[u][c];
	}
	exist[u][num]=1;
}
in int find(char *s)
{
	int len=strlen(s),u=1,i,c,f=0;
	for(i=0;i<len;++i){
		c=s[i]-'a';
		if(!ch[u][c]){
			f=1;break;
		}
		u=ch[u][c];
	}
	if(!f)
		for(i=1;i<=n;++i)
			if(exist[u][i])cout<<i<<" ";
	cout<<endl;
}
int main()
{
	int i,j;n=read();
	for(i=1;i<=n;++i){
		l=read();
		for(j=1;j<=l;++j)
			cin>>s,insert(s,i);
	}
	m=read();
	for(i=1;i<=m;++i)cin>>s,find(s);
}
2024/7/27 14:42
加载中...