BZOJ 3676

传送门

首先搞出来后缀自动机并统计以后缀自动机中每个节点为结尾的子串个数

然后用manacher找回文串,将每个找到的回文串用自动机统计出出现次数

然后就没了…


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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
program bzoj_3676;
const maxn=300001;
var fa:array[0..maxn*2,0..20]of longint;
cnt:array[0..maxn*2]of int64;
son:array[0..maxn*2,1..26]of longint;
n,tot,last,logn:longint;
str:array[0..maxn]of char;
l,tmp,seq,p:array[0..maxn*2]of longint;
pos:array[1..maxn]of longint;
ans:int64;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end;
procedure extend(c,t:longint);
var i,p,q,np,nq:longint;
begin
p:=last;
inc(tot);
np:=tot;
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:=1 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,j:longint;
begin
for i:=0 to n do tmp[i]:=0;
for i:=1 to tot do inc(tmp[l[i]]);
for i:=1 to n do inc(tmp[i],tmp[i-1]);
for i:=tot downto 1 do
begin
seq[tmp[l[i]]]:=i;
dec(tmp[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]]);
logn:=0;
while 1<<logn<=n do inc(logn);
for i:=1 to tot do
for j:=1 to logn do fa[i,j]:=fa[fa[i,j-1],j-1];
ans:=0;
end;
procedure query(st,ed:longint);
var p,i:longint;
begin
p:=pos[ed];
for i:=logn downto 0 do if l[fa[p,i]]>=ed-st+1 then p:=fa[p,i];
ans:=max(ans,int64(cnt[p])*int64(ed-st+1));
end;
procedure manacher;
var i,mx,id:longint;
begin
str[0]:='_';
str[n+1]:='-';
mx:=0;
id:=0;
for i:=1 to n do
begin
if mx>i then p[i]:=min(p[id<<1-i],mx-i) else p[i]:=0;
while str[i+p[i]]=str[i-p[i]] do
begin
query(i-p[i],i+p[i]);
inc(p[i]);
end;
if i+p[i]>mx then
begin
mx:=i+p[i];
id:=i;
end;
end;
mx:=0;
for i:=1 to n do
begin
if mx>i then p[i]:=min(p[id<<1-i],mx-i-1) else p[i]:=0;
while str[i+p[i]+1]=str[i-p[i]] do
begin
query(i-p[i],i+p[i]+1);
inc(p[i]);
end;
if i+p[i]>mx then
begin
mx:=i+p[i];
id:=i;
end;
end;
end;
begin
n:=0;
tot:=1;
l[1]:=0;
last:=1;
while not eoln do
begin
inc(n);
read(str[n]);
extend(ord(str[n])-96,n);
end;
init;
manacher;
writeln(ans);
end.