[回文自动机] BZOJ3676 [Apio2014] . 回文串

回文自动机裸题。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300005;
int n,a[maxn];
int lst,N_PT,plen[maxn],fail[maxn],cnt[maxn],ch[maxn][26];
char s[maxn];
int newnode(int t){
N_PT++; cnt[N_PT]=0; plen[N_PT]=t;
for(int i=0;i<=25;i++) ch[N_PT][i]=0;
return N_PT;
}
void Init(){
N_PT=-1; newnode(0); newnode(-1); a[0]=-1;
fail[0]=1; fail[1]=1; lst=0;
}
int toFail(int x,int n){
while(a[n-1-plen[x]]!=a[n]) x=fail[x];
return x;
}
void Insert(int c,int n){
c-='a'; a[n]=c; int p=toFail(lst,n);
if(!ch[p][c]){
int v=newnode(plen[p]+2);
fail[v]=ch[toFail(fail[p],n)][c];
ch[p][c]=v;
}
cnt[lst=ch[p][c]]++;
}
LL ans;
int main(){
freopen("bzoj3676.in","r",stdin);
freopen("bzoj3676.out","w",stdout);
scanf("%s",s+1); int n=strlen(s+1);
Init();
for(int i=1;i<=n;i++)
Insert(s[i],i);
for(int i=N_PT;i>=1;i--){
cnt[fail[i]]+=cnt[i]; ans=max(ans,(LL)plen[i]*cnt[i]);
}
printf("%lld\n",ans);
return 0;
}