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:longint;
fa,s,next,d,fr:array[1..1000000] of longint;
c:array[1..1000000] of char;
word:array[1..200] of longint;
e:array[1..1000000,1..2] of longint;
procedure build_trie;
var
now,i:longint;
begin
sum:=1;
for i:=1 to n do begin
now:=1;
repeat
read(ch);
if b[now,ch]=0 then begin
inc(sum);
b[now,ch]:=sum;
c[sum]:=ch;
fa[sum]:=now;
now:=sum;
end
else now:=b[now,ch];
inc(s[now]);
until eoln;
word[i]:=now;
readln;
end;
end;
procedure add(x,y:longint);
begin
inc(edge); e[edge,1]:=y; e[edge,2]:=fr[x]; fr[x]:=edge;
end;
function get_next(x:longint):longint;
begin
if (b[x,c[k]]<>0) and (b[x,c[k]]<>k) then exit(b[x,c[k]]);
if x=1 then exit(1) else get_next:=get_next(next[x]);
end;
procedure build_ac;
var
h,t,i:longint;
begin
h:=0; t:=1; d[t]:=1; next[1]:=1;
repeat
inc(h);
k:=d[h];
if k<>1 then next[k]:=get_next(fa[k]);
for ch:='a' to 'z' do
if b[k,ch]<>0 then begin inc(t); d[t]:=b[k,ch]; end;
until h=t;
for i:=2 to sum do add(next[i],i);
end;
procedure dfs(x:longint);
var
k:longint;
begin
k:=fr[x];
while k<>0 do begin
dfs(e[k,1]);
s[x]:=s[x]+s[e[k,1]];
k:=e[k,2];
end;
end;
begin
readln(n);
build_trie;
build_ac;
dfs(1);
for i:=1 to n do writeln(s[word[i]]);
end.