【题解】[TJOI2010] 阅读理解

题目信息
分析
Code

题目信息

题目来源：CCF 天津省选 2010；

在线评测地址：Luogu#3879；

运行限制：时间 (2.00 extrm{s})，空间限制 (128 extrm{MiB})。

题目描述

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

输入格式

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

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

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

输出格式

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

数据规模与约定

对于 (30\%) 的数据，(1le Mle 10^3)。
对于 (100\%) 的数据，(1le Mle 10^4)，(1le Nle 10^3)。

每篇短文长度（含相邻单词之间的空格）(le 5 imes 10^3) 字符，每个单词长度 (le 20) 字符。

分析

这道题的一个特点就是要在时间与空间取平衡，从而最大化效率。

(30)- ( exttt{pts})

暴力思路，对于每一个询问去扫前面所有的文章。复杂度 (mathcal{O}(Msum |S|))，估计连部分分都拿不到。

(30 exttt{pts})

用一个 set 记录每一篇文章有的字符串。每一次询问时，分别去每一个 set 里查询是否存在即可。

复杂度是 (mathcal{O}(NM|s|log L))，相比于前面的做法优秀很多，如果复杂度优秀的话可以勉强 AC，但并不是最好的做法。

(100 exttt{pts})

Solution 1

如果有比 set 更好的维护字符串的数据结构，不难想到 Trie。如果我们用 Trie 维护这些字符串呢？单次复杂度就能省去一个 (log)，只有 (mathcal{O}(NM|s|))。吸了氧气以后能跑进 (100 extrm{ms})，是一种很好的做法。

Solution 2

其实这道题有很多时间复杂度很优秀的做法，但是大多都由于空间限制被枪毙了。

比如说，维护一个 Trie，每个节点连接着一个数组，记录着以这个节点结束的字符串所在文章的集合。单次询问复杂度只有询问字符串长度。

但是，一个 Trie 内有巨量的节点，而且放了所有的字符串，爆空间是在所难免的事。

这时，我们可以退而求其次，转而用 map 这种空间常数较小的数据结构来维护。每一个 string 指向一个集合，用 vector 维护，复杂度是 (mathcal{O}left((N+M)|s|log sum L ight))。实际运行常数较大。

Code

这里使用了第一种做法。

洛谷提交记录（R37723587）

#include <cstdio>
#include <vector>
using namespace std;

constexpr int max_n = 1000, max_l = 20;
char tmp[max_l+1]; // 临时存储，用来给函数传参

struct node // 字典树节点
{
	bool is_end;
	int son[26];

	node() : is_end(false)
	{
		for (int i = 0; i < 26; i++)
			son[i] = -1;
	}
};

struct trie // 一棵字典树
{
	vector<node> tr; // 树

	trie() { }

	void clear(int len)
	{
		tr.assign(len, node());
	}

	void insert() // 插入
	{
		int ptr = 0;

		for (int i = 0; tmp[i]; i++) // 寻路
		{
			if (tr[ptr].son[tmp[i]-'a'] != -1) // 有子节点
				ptr = tr[ptr].son[tmp[i]-'a']; // 继续走
			else // 没有子节点
			{
				ptr = tr[ptr].son[tmp[i]-'a'] = tr.size(); // 新建一个，并继续走。
				tr.push_back(node());
			}
		}

		tr[ptr].is_end = true; // 打上标记
	}

	bool askif() // 询问是否存在
	{
		int ptr = 0;

		for (int i = 0; tmp[i]; i++) // 寻路
		{
			if (tr[ptr].son[tmp[i]-'a'] == -1) // 没有子节点
				return false; // 字符串不存在
			else
				ptr = tr[ptr].son[tmp[i]-'a']; // 有就继续走
		}

		return tr[ptr].is_end; // 是结尾就存在
	}
};

trie passages[max_n]; // 一篇文章建一棵树

int main()
{
	int n, m, cnt;
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &cnt);

		passages[i].clear(1);
		for (int j = 0; j < cnt; j++)
		{
			scanf("%s", tmp);
			passages[i].insert(); // 输入并插入
		}
	}

	scanf("%d", &m);
	for (int i = 0; i < m; i++) // 处理询问
	{
		scanf("%s", tmp);

		for (int j = 0; j < n; j++)
			if (passages[j].askif())
				printf("%d ", j + 1); // 存在就输出，默认升序
		
		putchar('
'); // 不需要加上标记，没有就留空行
	}

	return 0; // 然后就 AC 了、
}