【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 46 47 48 49 50 51 52 53 54 |
// <3676.cpp> - Wed Mar 8 09:18:15 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=300010; const int INF=1e9; const int S=26; char s[MAXN]; int n,t,b[MAXN][S],f[MAXN],len[MAXN],cnt[MAXN]; void build(){ t=2;len[1]=-1;f[0]=1; int p=0; for(int i=1;i<=n;i++){ while(s[i]!=s[i-len[p]-1])p=f[p]; if(!b[p][s[i]]){ len[t]=len[p]+2; int g=f[p]; while(s[i]!=s[i-len[g]-1])g=f[g]; f[t]=b[g][s[i]]; b[p][s[i]]=t++; } cnt[p=b[p][s[i]]]++; } } int main(){ scanf("%s",s+1); n=strlen(s+1); s[0]=-1;for(int i=1;i<=n;i++)s[i]-='a'; build(); for(int i=t-1;i;i--)cnt[f[i]]+=cnt[i]; lol ans=0; for(int i=2;i<t;i++)ans=max(ans,1ll*len[i]*cnt[i]); printf("%lld",ans); return 0; } |