社区讨论

Trie全RE求助

P3879[TJOI2010] 阅读理解参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lprpbzyu
此快照首次捕获于
2023/12/05 10:09
2 年前
此快照最后确认于
2023/12/05 16:04
2 年前
查看原帖
玄关
CPP
#include<bits/stdc++.h>
//#define int __int128
using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),
		ch=getchar();
	return x*f;
}

inline void write(int n)
{
	if(n<0)
		n=-n,
		putchar('-');
	if(n>=10)
		write(n/10);
	putchar(n%10+'0');
	return ;
}

const int N=10010;

struct node
{
	int child[30];
	bool cnt[1010];
}Trie[N];

int n,m;
int tot=1;
int st[N],top=0;

void insert(string s,int art)
{
	int cur=0;
	for(int i=0;s[i];i++)
	{
		if(Trie[cur].child[s[i]-'a']==0)
			Trie[cur].child[s[i]-'a']=tot++;
		cur=Trie[cur].child[s[i]-'a'];
	}
	Trie[cur].cnt[art]=1;
	return ;
}

void query(string s)
{
	int cur=0,flag=0;
	for(int i=0;s[i];i++)
	{
		if(Trie[cur].child[s[i]-'a']==0)
		{
			flag=1;
			break;
		}
		cur=Trie[cur].child[s[i]-'a'];
	}
	if(flag)
	{
		putchar('\n');
		return ;
	}
	top=0;
	bool f=0;
	for(int i=1;i<=n;i++)
		if(Trie[cur].cnt[i])
		{
			if(f) putchar(' ');
			else f=1;
			write(i);
		}
	if(top)
		write(st[0]);
	for(int i=1;i<top;i++)
		putchar(' '),
		write(st[i]);
	putchar('\n');
	return ;
}

signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		int L=read();
		while(L--)
		{
			string s;
			cin>>s;
			insert(s,i);
		}
	}
	m=read();
	map<string,bool> dic;
	while(m--)
	{
		string s;
		cin>>s;
		if(dic[s])
			continue;
		dic[s]=1;
		query(s);
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...