BZOJ

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.