BZOJ 3172

传送门

额…建出来SAM,然后直接统计就行了


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
program bzoj_3172;
const maxn=1000200<<1+1;
var son:array[1..maxn,0..26]of longint;
fa:array[0..maxn,0..20]of longint;
l,cnt,pos,seq,c:array[0..maxn]of longint;
n,i,j,tot,p,q,np,nq,last,logn,totlen,len:longint;
ed:array[0..200]of longint;
ch:char;
procedure extend(c,t:longint);
var i:longint;
begin
inc(tot);
np:=tot;
p:=last;
last:=tot;
l[np]:=l[p]+1;
cnt[np]:=1;
pos[t]:=tot;
while (p<>0)and(son[p,c]=0) do
begin
son[p,c]:=np;
p:=fa[p,0];
end;
if p=0 then fa[np,0]:=1 else
begin
q:=son[p,c];
if l[p]+1=l[q] then fa[np,0]:=q else
begin
inc(tot);
nq:=tot;
l[nq]:=l[p]+1;
for i:=0 to 26 do son[nq,i]:=son[q,i];
fa[nq,0]:=fa[q,0];
fa[q,0]:=nq;
fa[np,0]:=nq;
while (p<>0)and(son[p,c]=q) do
begin
son[p,c]:=nq;
p:=fa[p,0];
end;
end;
end;
end;
procedure init;
var i:longint;
begin
logn:=0;
while 1<<logn<=totlen do inc(logn);
for j:=1 to logn do
for i:=1 to tot do fa[i,j]:=fa[fa[i,j-1],j-1];
for i:=0 to totlen do c[i]:=0;
for i:=1 to tot do inc(c[l[i]]);
for i:=1 to totlen do inc(c[i],c[i-1]);
for i:=tot downto 1 do
begin
seq[c[l[i]]]:=i;
dec(c[l[i]]);
end;
for i:=tot downto 1 do if fa[seq[i],0]>1 then inc(cnt[fa[seq[i],0]],cnt[seq[i]]);
end;
function query(st,ed:longint):longint;
var i,p:longint;
begin
p:=pos[ed];
for i:=logn downto 0 do if l[fa[p,i]]>=ed-st+1 then p:=fa[p,i];
exit(cnt[p]);
end;
begin
readln(n);
tot:=1;
l[1]:=0;
fa[1,0]:=0;
last:=1;
totlen:=0;
for i:=1 to n do
begin
len:=0;
while not eoln do
begin
inc(len);
read(ch);
extend(ord(ch)-96,totlen+len);
end;
inc(totlen,len);
ed[i]:=totlen;
if i<>n then
begin
inc(totlen);
extend(0,0);
end;
readln;
end;
init;
ed[0]:=-1;
for i:=1 to n do writeln(query(ed[i-1]+2,ed[i]));
end.