Description
某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。每个单词由小写字母组成,N<=200,单词总长度不超过10^6。
Analysis
建出AC自动机,然后对于一个点i和它的Fail[i]反向连边。这样构造出来的是一个树。
对于一个单词它出现的次数就是这个单词的结尾节点X的子树大小。证明是容易的。
不过这里的子树大小指的是每一个节点被访问过的次数和...
上代码:
var
b:array[1..1000000,'a'..'z'] of longint;
ch:char;
i,edge,sum,n,k:longin......
阅读全文