Trie树【P3879】 [TJOI2010]阅读理解

Description

英语老师留了N篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。

Input

第一行为整数N，表示短文篇数，其中每篇短文只含空格和小写字母。

按下来的N行，每行描述一篇短文。每行的开头是一个整数L，表示这篇短文由L个单词组成。接下来是L个单词，单词之间用一个空格分隔。

然后为一个整数M，表示要做几次询问。后面有M行，每行表示一个要统计的生词。

Output

对于每个生词输出一行，统计其在哪几篇短文中出现过，并按从小到大输出短文的序号，序号不应有重复，序号之间用一个空格隔开（注意第一个序号的前面和最后一个序号的后面不应有空格）。如果该单词一直没出现过，则输出一个空行。

裸的\(Trie\)树,结果被卡空间？？？

搞得要开\(bitset\)。

我们对于每一个位置记录其在哪出现过。

我们记录\(b[x][i]\)代表当前这个单词的结尾\(x\)是否在\(i\)行出现过。

最后查询的时候直接枚举即可。

代码

#include<cstdio>

#include<bitset>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

const int gz=300001;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int ch[gz][26],idx,n,m;

bitset<1001> b[gz];

char s[31];

inline void insert(R char *s,R int x)

{

	R int u=0;

	for(R int i=0;s[i];i++)

	{

		R int v=s[i]-'a';

		if(!ch[u][v])ch[u][v]=++idx;

		u=ch[u][v];

	}

	b[u][x]=true;

}

inline void query(R char *s)

{

	R int u=0;

	for(R int i=0;s[i];i++)

	{

		R int v=s[i]-'a';

		if(!ch[u][v]){goto he;}

		u=ch[u][v];

	}

	for(R int i=1;i<=n;i++)

		if(b[u][i])printf("%d ",i);

	he :;

	puts("");

}

int main()

{

	in(n);

	for(R int i=1,x;i<=n;i++)

	{

		in(x);

		for(R int j=1;j<=x;j++)

		{

			scanf("%s",s);

			insert(s,i);

		}

	}

	in(m);

	for(R int i=1;i<=m;i++)

	{

		scanf("%s",s);

		query(s);

	}

}

巴特西

Trie树【P3879】 [TJOI2010]阅读理解

Description

Input

Output

最新文章

热门文章