Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

01/11
11:08
AC自动机 字符串

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

HINT

 

Source

Solution

朴素的做法是建好AC自动机之后,拿每一个串匹配,把路径上的点都cnt++,统计答案,然而会被卡死。 正解:将fail反向,成为一棵以0为根节点的fail树,然后向树根扫一遍,O(n)统计答案