给出一个单词集，其中含有 \(500\) 个长度为 \(200\) 的单词串。之后给出 \(1000\) 个长度为 \(10000\) 的文本串，询问每个文本串中出现了哪些单词集中的单词（每个文本串中最多出现 \(3\) 个单词）。字母串中的字符均为为 ASCII 码可见字符。
不难看出，这道题目是一道可以用 AC 自动机解决的题目。具体做法不再赘述。这里我想讨论的，是使用 AC 自动机解决这道题目时的时间、空间复杂度。
这道题目的时间限制（C++）为 \(1000MS\)， 内存限制（C++）为 \(32MB\)。 仔细计算一下不难发现，这道题目的时间、空间都比较紧张。
AC 自动机的时间复杂度与树上节点个数 \(\times\) 每个节点的儿子个数成正比。这道题目中，节点个数为 \(500 \times 200 = 10^5\)，每个节点的儿子个数为不同的字符个数，这里包括所有的 ASCII 可见字符，约为 \(100\) 个。因此，只在树上做一次 bfs，时间复杂度就有 \(10^5 \times 100 = 10^7\)。
另外，还要记录每个节点上包含的单词。这里有一个优化方法。因为每个文本串最多包含 \(3\) 个单词，所以每个节点只需要保存 \(3\) 个单词就可以了。在 bfs 过程中，将父节点的单词传递给下一个节点的复杂度为 \(3 \times 3 = 9\)，这样整个时间复杂度就是 \(9 \times 10^7\)。
这个时间复杂度，是让人有些慌，感觉稍不留神就会被卡时间。但计算完空间复杂度，你就不会这么慌了。
你会更慌。
AC 自动机的空间复杂度，基本上是树上节点个数 \(\times\) 每个节点的儿子个数。如果每个节点的儿子使用 int 类型来保存，那就是 \(4 \times 10^7B = 40MB\)。而题目内存限制是 \(32MB\)，使用int会超出内存限制。
不过后来的事实证明，这道题目的数据比较弱，使用int类型便可以通过这道题目，实际内存使用只有 \(24MB\)。（所以这题面算不算虚假宣传）
当然在刚开始做这道题的时候，没敢使用int类型直接提交。思考了很久该使用什么类型，最后决定使用bitset。
因为树上的节点总数有 \(10^5\) 个，需要覆盖所有的节点，所以我使用了bitset<17>。这时我幻想的空间复杂度是：\(\frac{17}{8} \times 10^7 \approx 20MB\)。
写完。提交。Memory Limit Exceeded。内存使用 \(40MB\)。
（无数）事实证明，不要对 STL 的时间、空间复杂度抱有幻想。
26 April 2017