trie 10*WA+1*RE求助
查看原帖
trie 10*WA+1*RE求助
513326
阿哲朗读楼主2022/4/21 20:55
#include<bits/stdc++.h>
using namespace std;
int cnt;
int n,m;
struct tree
{
	int ch[26];
	bool flag=0,book[101];
	void insert()
	{
		memset(ch,0,sizeof(ch));
		memset(book,0,sizeof(book));
	}
}a[500001];
void add(string s,int k)
{
	int dad=0;
	for(int i=0;i<s.length();i++)
	{
		int kid=s[i]-'a';
		if(a[dad].ch[kid]==0)
		{
			a[dad].ch[kid]=++cnt;
			dad=cnt;
			a[dad].insert();
		}
		else
		{
			dad=a[dad].ch[kid];
		}
	}
	a[dad].flag=1;
	a[dad].book[k]=1;
}
void check(string s)
{
	int dad=0;
	for(int i=0;i<s.length();i++)
	{
		int kid=s[i]-'a';
		if(a[dad].ch[kid]==0)
		{
			cout<<endl;
			return;
		}
		else
		{
			dad=a[dad].ch[kid];
		}
	}
	if(!a[dad].flag) cout<<endl;
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(a[dad].book[i])
				cout<<i<<" ";
		}
	}
	return ;
}
int main()
{
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		int k;
		cin>>k;
		for(int j=1;j<=k;j++)
		{
			cin>>s;
			add(s,i);
		}
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		string s1;
		cin>>s1;
		check(s1);
	}
	return 0;
}
2022/4/21 20:55
加载中...