[HDUOJ 2896] 病毒侵袭


返回首页

题意描述

给出一个单词集,其中含有 500 个长度为 200 的单词串。之后给出 1000 个长度为 10000 的文本串,询问每个文本串中出现了哪些单词集中的单词(每个文本串中最多出现 3 个单词)。字母串中的字符均为为 ASCII 码可见字符。

题目分析

不难看出,这道题目是一道可以用 AC 自动机解决的题目。具体做法不再赘述。这里我想讨论的,是使用 AC 自动机解决这道题目时的时间、空间复杂度。

这道题目的时间限制(C++)为 1000MS, 内存限制(C++)为 32MB。 仔细计算一下不难发现,这道题目的时间、空间都比较紧张。

时间复杂度

AC 自动机的时间复杂度与树上节点个数 × 每个节点的儿子个数成正比。这道题目中,节点个数为 500×200=105,每个节点的儿子个数为不同的字符个数,这里包括所有的 ASCII 可见字符,约为 100 个。因此,只在树上做一次 bfs,时间复杂度就有 105×100=107

另外,还要记录每个节点上包含的单词。这里有一个优化方法。因为每个文本串最多包含 3 个单词,所以每个节点只需要保存 3 个单词就可以了。在 bfs 过程中,将父节点的单词传递给下一个节点的复杂度为 3×3=9,这样整个时间复杂度就是 9×107

这个时间复杂度,是让人有些慌,感觉稍不留神就会被卡时间。但计算完空间复杂度,你就不会这么慌了。

你会更慌。

空间复杂度

AC 自动机的空间复杂度,基本上是树上节点个数 × 每个节点的儿子个数。如果每个节点的儿子使用 int 类型来保存,那就是 4×107B=40MB。而题目内存限制是 32MB,使用int会超出内存限制。

不过后来的事实证明,这道题目的数据比较弱,使用int类型便可以通过这道题目,实际内存使用只有 24MB。(所以这题面算不算虚假宣传)

代码

当然在刚开始做这道题的时候,没敢使用int类型直接提交。思考了很久该使用什么类型,最后决定使用bitset

bitset 的内存使用

因为树上的节点总数有 105 个,需要覆盖所有的节点,所以我使用了bitset<17>。这时我幻想的空间复杂度是:178×10720MB

写完。提交。Memory Limit Exceeded。内存使用 40MB

失败代码

(无数)事实证明,不要对 STL 的时间、空间复杂度抱有幻想。

26 April 2017