BZOJ 3172: [Tjoi2013]单词(AC自动机+fail树)

Description

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

Input

第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N<=200,单词长度不超过10^6 Output 输出N个整数,第i行的数字表示第i个单词在文章中出现了多少次。 Sample Input 3 a aa aaa Sample Output 6 3 1 重新温习了一下AC自动机。 众所周知,AC自动机上一个节点对应了一个字符串的前缀,而fail指针的跳则对应了某个字符串的后缀,所以如果我们把fail指针反向建图,会得到一棵树,也就是fail树。每个点父节点的字符串都是这个点字符串的后缀,并且树上没有更长的它的后缀。 那么这道题目我们在插入字符串的时候,把经过的每个节点的cnt加1,然后在求fail指针的过程中建立fail树。那么我们只需要统计出来某个节点的子树cnt之和,便是他在别的字符串内出现的次数了,因为这个节点是子树所有节点所代表的字符串的后缀。

发表评论

电子邮件地址不会被公开。 必填项已用*标注