AC. 梦想

frank_c1

[BZOJ 3172] 单词

发布于2015年11月22日 | 暂无评论 | 981阅读 | AC自动机,字符串

题目描述

某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。

输入格式

第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N<=200,单词长度不超过10^6。

输出格式

输出N个整数,第i行的数字表示第i个单词在文章中出现了多少次。

题目解析

刚学会AC自动机时,我很兴奋,马上到网上找了一道题来做(就是这道题)。当我兴奋地打完、上交,然后就TLE了……QAQ

这个题的朴素算法就是建立所有串的AC自动机,然后每个串上去跑一遍,然后统计答案。当然是TLE的。正解是用Fail树,利用树的性质来减少重复的计算。

首先根据AC自动机中失配指针的定义,每一个结点有且仅有一个失配指针指向另一结点,即所有结点出度为1。而对于某一结点u,它一定是由它的前趋结点或者失配指针指向u的结点转移过来的。那么考虑把所有的失配指针反向,然后把反向后的失配指针当作边,我们就得到了一棵以结点0为根的树(因为所有结点入度为1)。这样利用树的性质,我们dfs一遍就可以求出答案了。

设结点i出现在cnt[i]个单词中,插入单词时所有经过的结点cnt[u]++,构造出Fail树后dfs一遍,答案是单词末结点子树的cnt值总和。