10分求助
查看原帖
10分求助
184464
LLMS15楼主2020/5/12 21:41

对询问建立的TrieTrie,最后一个点A了,其他点都WA了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#define maxn 1000
#define maxm 10000
#define maxs 200000
using namespace std;
int read()
{
	char c = getchar();
	int s = 0,w = 1;
	while(c < '0' || c > '9')
	{
		if(c == '-') w = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		s = (s * 10) + (c - '0');
		c = getchar();
	}
	return w * s;
}
void write(int x)
{
	if(x > 9) write(x / 10);
	putchar((x % 10) + '0');
}
int n,m;
int t[maxs + 10][26],tot = 1;
vector<int> f[maxs + 10];
string a[maxn + 10][250];
int l[maxn + 10];
bool flag[maxm + 10];
vector<int> ans[maxm + 10];
void ins(string s,int x)
{
	int len = s.size(),p = 1;
	for(int i = 0;i < len;i++)
	{
		int c = s[i] - 'a';
		if(t[p][c] == 0) t[p][c] = ++tot;
		p = t[p][c];
	}
	f[p].push_back(x);
}
int search(string s)
{
	int len = s.size(),p = 1;
	for(int i = 0;i < len;i++)
	{
		int c = s[i] - 'a';
		p = t[p][c];
		if(p == 0) return 0;
	}
	return p;
}
int main()
{
	//freopen("data.in","r",stdin);
	//freopen("my.out","w",stdout);
	n = read();
	for(int i = 1;i <= n;i++)
	{
		l[i] = read();
		for(int j = 1;j <= l[i];j++)
		{	
			cin>>a[i][j];
		}
	}
	m = read();
	for(int i = 1;i <= m;i++)
	{
		string s;
		cin>>s;
		ins(s,i);
	}
	for(int i = 1;i <= n;i++)
	{
		memset(flag,false,sizeof(flag));
		for(int j = 1;j <= l[i];j++)
		{	
			int x = search(a[i][j]);
			if(x == 0) continue;
			for(int k = 0;k < f[x].size();k++)
			{
				if(flag[f[x][k]]) continue;
				ans[f[x][k]].push_back(i);
				flag[f[x][k]] = true;
			}
		}
	}
	for(int i = 1;i <= m;i++)
	{
		for(int j = 0;j < ans[i].size();j++)
		{
			write(ans[i][j]);
			putchar(' ');
		}
		putchar('\n');
	} 
	return 0;
}
2020/5/12 21:41
加载中...