BZOJ

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.