HarmoniikaaHarmoniikaa UOJ 103

#include<algorithm>
#include<cstring>
#define N 300010
using namespace std;
char ch[N];
int n;
struct {
  int to[N][26],f[N],l[N],right[N],last,cnt;
  PAM(){l[1]=-1;f[0]=cnt=1;}
  void extend(int c,int n){
    int p=last;
    while(ch[n]!=ch[n-l[p]-1]) p=f[p];
    if(!to[p][c]){
      int np=++cnt,k=f[p];l[np]=l[p]+2;
      while(ch[n]!=ch[n-l[k]-1]) k=f[k];
      f[np]=to[k][c];to[p][c]=np;
    }
    right[last=to[p][c]]++;
  }
  long long calc(){
    long long ans=0;
    for(int i=cnt;i>=0;i--) right[f[i]]+=right[i],ans=max(ans,(long long)right[i]*l[i]);
    return ans;
  }
}P;
int main(){
  scanf("%s",ch+1);
  n=strlen(ch+1);
  for(int i=1;i<=n;i++) P.extend(ch[i]-'a',i);
  printf("%lldn",P.calc());
  return 0;
}