trie树求调,悬关
查看原帖
trie树求调,悬关
629377
iamajcer楼主2024/3/1 13:20
#include <bits/stdc++.h>
using namespace std;

const int N=500010, M=25;
int n, L, t, trie[N][M], idx=0;
bool st[N][110]; 
char s[M];
void insert(char c[], int x)
{
	int p=0;
	for (int i=1; i<=strlen(c+1); i++)
	{
		int u=c[i]-'a'+1;
		if (!trie[p][u]) trie[p][u]=++idx;
		p=trie[p][u];
	}
	st[p][x]=1;
}
void query(char c[])
{
	int p=0, flag=1;
	for (int i=1; i<=strlen(c+1); i++)
	{
		int u=c[i]-'a'+1;
		if (!trie[p][u])
		{
			flag=0;
			break;
		}
		p=trie[p][u];
	}
	if (flag)
	{		
		for (int i=1; i<=n; i++)
			if (flag && st[p][i]) printf("%d", i), flag=0;
			else if (st[p][i]) printf(" %d", i);
	}
	puts("");
}
int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++)
	{
		scanf("%d", &L);
		for (int j=1; j<=L; j++) 
		{
			cin>>(s+1);
			insert(s, i);
		}	
	}
	scanf("%d", &t);
	while (t--)
	{
		cin>>(s+1);
		query(s);
	}
	return 0;
}

https://www.luogu.com.cn/record/148838294

A了两个点,其他全WA

2024/3/1 13:20
加载中...