考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出 
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最 
大出现值。 

输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。 

输出一个整数，为逝查回文子串的最大出现值。 

一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。 

在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中： 

● a出现4次，其出现值为4：1：1=4 

● b出现2次，其出现值为2：1：1=2 

● c出现1次，其出现值为l：1：l=l 

● aba出现2次，其出现值为2：1：3=6 

● aca出现1次，其出现值为1=1：3=3 

●bacab出现1次，其出现值为1：1：5=5 

● abacaba出现1次，其出现值为1：1：7=7 

故最大回文子串出现值为7。 

【数据规模与评分】 

数据满足1≤字符串长度≤300000。

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=350100;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 char s[mxn];17 long long ans=0;18 struct HWM{19     int t[mxn][26];20     int fa[mxn];21     int l[mxn],sz[mxn];22     int S,cnt,last;23     void init(){24         S=cnt=last=fa[0]=fa[1]=1;l[1]=-1;25         return;26     }27     void add(int c,int n){28         int p=last;29         for(;s[n-l[p]-1]!=s[n];p=fa[p]);30         if(!t[p][c]){31             int np=++cnt;l[np]=l[p]+2;32             int k=fa[p];33             while(s[n-l[k]-1]!=s[n])k=fa[k];34             fa[np]=t[k][c];//35             t[p][c]=np;36         }37         last=t[p][c];38         ++sz[last];39         return;40     }    41     void solve(){42         for(int i=cnt;i;i--){43             sz[fa[i]]+=sz[i];44             long long tmp=(long long)sz[i]*l[i];45             if(tmp>ans)ans=tmp;46         }47         return;48     }49 }hw;50 int main(){51     int i,j;52     scanf("%s",s+1);53     hw.init();54     int len=strlen(s+1);55     for(i=1;i<=len;i++) hw.add(s[i]-‘a‘,i);56     hw.solve();57     printf("%lld\n",ans);58     return 0;59 }