ural 1297. Palindrome

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005;
char sr[N];
int sa[N],wa[N<<1],wb[N<<1],to[N],f[13][N];
int ask(int l,int r)
{
    int k=0;
    for(;1<<(k+1)<=r-l+1;++k);
    return min(f[k][l],f[k][r-(1<<k)+1]);
}
int main()
{
    scanf("%s",sr);
    int l=strlen(sr),n=2*l+1,m=128,*x=wa,*y=wb,mx=0,wz;
    sr[l]=‘0‘;
    for(int i=l+1;i<n;++i) sr[i]=sr[2*l-i];
    for(int i=0;i<n;++i) ++to[x[i]=sr[i]];
    for(int i=1;i<m;++i) to[i]+=to[i-1];
    for(int i=n-1;i>=0;--i) sa[--to[x[i]]]=i;
    for(int j=1,p=0;p<n;m=p,j<<=1)
    {
        p=0;
        for(int i=n-j;i<n;++i) y[p++]=i,x[i+j]=-1;;
        for(int i=0;p<n;++i) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(int i=0;i<m;++i) to[i]=0;
        for(int i=0;i<n;++i) ++to[x[y[i]]];
        for(int i=1;i<m;++i) to[i]+=to[i-1];
        for(int i=n-1;i>=0;--i) sa[--to[x[y[i]]]]=y[i];
        int *t=x;x=y;y=t;
        x[sa[0]]=0;
        for(int i=p=1;i<n;++i)
            y[sa[i]]!=y[sa[i-1]]||y[sa[i]+j]!=y[sa[i-1]+j]?x[sa[i]]=p++:x[sa[i]]=p-1;
    }
    for(int i=0,j,k=0;i<n;f[0][x[i++]]=k)
        if(!x[i]) k=0;
        else for(k?--k:0,j=sa[x[i]-1];i+k<n&&j+k<n&&sr[i+k]==sr[j+k];++k);
    for(int i=1;(1<<i)<=n;++i)
        for(int j=1;j+(1<<i)-1<=n;++j)
            f[i][j]=min(f[i-1][j],f[i-1][j+(1<<i-1)]);
    for(int i=0;i<l;++i)
    {
        int l=x[i],r=x[n-i-1];
        if(l>r) swap(l,r);
        int t=ask(l+1,r)*2-1;
        if(t>mx) mx=t,wz=i;
        if(i)
        {
            l=x[i];r=x[n-i];
            if(l>r) swap(l,r);
            t=ask(l+1,r)*2;
            if(t>mx) mx=t,wz=i;
        }
    }
    for(int i=wz-mx/2;i<=wz+mx/2-!(mx&1);++i)
        printf("%c",sr[i]);
    return 0;
}