1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 650000+5 26  27 #define maxm 20000000+5 28  29 #define eps 1e-10 30  31 #define ll long long 32  33 #define pa pair<int,int> 34  35 #define for0(i,n) for(int i=0;i<=(n);i++) 36  37 #define for1(i,n) for(int i=1;i<=(n);i++) 38  39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40  41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42  43 #define mod 1000000007 44  45 using namespace std; 46  47 inline int read() 48  49 { 50  51     int x=0,f=1;char ch=getchar(); 52  53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54  55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56  57     return x*f; 58  59 } 60 int n,m; 61 int t1[maxn],t2[maxn],c[maxn],a[maxn],sa[maxn],rk[maxn],h[maxn],st[maxn][20]; 62 int b[maxn],p[maxn]; 63 char s[maxn]; 64 void getsa(int m) 65 { 66     int *x=t1,*y=t2; 67     for0(i,m)c[i]=0; 68     for0(i,n)c[x[i]=a[i]]++; 69     for1(i,m)c[i]+=c[i-1]; 70     for3(i,n,0)sa[--c[x[i]]]=i; 71     for(int k=1;k<=n+1;k<<=1) 72     { 73         int p=0; 74         for2(i,n-k+1,n)y[p++]=i; 75         for0(i,n)if(sa[i]>=k)y[p++]=sa[i]-k; 76         for0(i,m)c[i]=0; 77         for0(i,n)c[x[y[i]]]++; 78         for1(i,m)c[i]+=c[i-1]; 79         for3(i,n,0)sa[--c[x[y[i]]]]=y[i]; 80         swap(x,y);p=0;x[sa[0]]=0; 81         for1(i,n)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p; 82         if(p>=n)break; 83         m=p; 84     } 85     for1(i,n)rk[sa[i]]=i; 86     for(int i=0,k=0,j;i<n;h[rk[i++]]=k) 87         for(k?k--:0,j=sa[rk[i]-1];a[i+k]==a[j+k];k++); 88 } 89 void getst() 90 { 91     int k=log2(n); 92     for1(i,n)st[i][0]=h[i]; 93     for1(j,k)for1(i,n-(1<<j)+1)st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); 94 } 95 inline int rmq(int x,int y) 96 { 97     int k=log2(y-x+1); 98     return min(st[x][k],st[y-(1<<k)+1][k]); 99 }100 inline ll query(int x,int y)101 {102     int l,r,mid,ql,qr;103     if(h[x+1]<y)qr=x;104     else105     {106         l=x+1;r=n;107         while(l<=r)108         {109             mid=(l+r)>>1;110             if(rmq(x+1,mid)>=y)l=mid+1;else r=mid-1;111         }112         qr=r;113     }114     if(h[x]<y)ql=x;115     else116     {117         l=1;r=x-1;118         while(l<=r)119         {120             mid=(l+r)>>1;121             //cout<<l<<‘ ‘<<mid<<‘ ‘<<r<<endl;122             if(rmq(mid+1,x)>=y)r=mid-1;else l=mid+1;123         }124         ql=l;125     }126     //cout<<x<<‘ ‘<<y<<‘ ‘<<ql<<‘ ‘<<qr<<endl;127     /*for2(i,sa[x],sa[x]+y-1)cout<<s[i];128     cout<<‘ ‘<<ql<<‘ ‘<<qr<<endl;*/129     return (ll)(qr-ql+1)*(ll)y;130 }131 132 int main()133 134 {135 136     freopen("input.txt","r",stdin);137 138     freopen("output.txt","w",stdout);139 140     scanf("%s",s);n=strlen(s);141     for0(i,n-1)a[i]=s[i]-‘a‘+1;a[n]=0;142     getsa(26);getst();143     for0(i,n-1)b[(i+1)<<1]=a[i];144     m=(n<<1)+1;145     int id=0,mx=0;ll ans=0;146     for1(i,m)147     {148         if(mx>i)p[i]=min(p[2*id-i],mx-i);149         while(i-p[i]-1>0&&i+p[i]+1<=m&&b[i-p[i]-1]==b[i+p[i]+1])p[i]++;150         if(i+p[i]>mx)151         {152             mx=i+p[i];153             id=i;154             ans=max(ans,query(rk[(i-p[i]-1)>>1],p[i]));155             //cout<<i<<‘ ‘<<p[i]<<‘ ‘<<(i-p[i]-1>>1)<<‘ ‘<<(rk[(i-p[i]-1)>>1])<<endl;156         }157     }158     //for1(i,m)cout<<i<<‘ ‘<<b[i]<<‘ ‘<<p[i]<<endl;159     printf("%lld\n",ans);160 161     return 0;162 163 }