ural1297

题解：

后缀数组

st表处理加速ｌｃｐ

把串后面加一个不可能出现的字符

然后再把串倒过来放在后面

暴力枚举中心

判断ｌｃｐ

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

int ws1[N],wv[N],wa[N],wb[N],rank1[N],height[N],sa[N],a[N],n,dp[N][];

char str[N];

int cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b]&&r[a+l]==r[b+l];

}

void da(int *r,int *sa,int n,int m)

{

    int *x=wa,*y=wb;

    for (int i=;i<m;i++)ws1[i]=;

    for (int i=;i<n;i++)ws1[x[i]=r[i]]++;

    for (int i=;i<m;i++)ws1[i]+=ws1[i-];

    for (int i=n-;i>=;i--)sa[--ws1[x[i]]]=i;

    for (int j=,p=;p<n;j*=,m=p)

     {

         p=;

        for (int i=n-j;i<n;i++)y[p++]=i;

        for (int i=;i<n;i++)

         if (sa[i]>=j)y[p++]=sa[i]-j;

        for (int i=;i<n;i++)wv[i]=x[y[i]];

        for (int i=;i<m;i++)ws1[i]=;

        for (int i=;i<n;i++)ws1[wv[i]]++;

        for (int i=;i<m;i++)ws1[i]+=ws1[i-];

        for (int i=n-;i>=;i--)sa[--ws1[wv[i]]]=y[i];

        p=;swap(x,y);x[sa[]]=;

        for (int i=;i<n;i++)x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

    }

}

void calheight(int *r,int *sa,int n)

{

    int j,k=;

    for (int i=;i<=n;i++)rank1[sa[i]]=i;

    for (int i=;i<n;height[rank1[i++]]=k)

     for (k?k--:,j=sa[rank1[i]-];r[i+k]==r[j+k];k++);

}

void RMQ()

{

    memset(dp,,sizeof(dp));

    for (int i=;i<=n*+;i++)dp[i][]=height[i];

    for (int j=;(<<j)<=*n+;j++)

     for (int i=;i+(<<j)-<=*n+;i++)

      dp[i][j]=min(dp[i][j-],dp[i+(<<(j-))][j-]);

}

int lcp(int l,int r)

{

    int a=rank1[l],b=rank1[r];

    if (a>b)swap(a,b);

    a++;

    int t=(int)(log(double(b-a+))/log(2.00));

    return min(dp[a][t],dp[b-(<<t)+][t]);

}

int main()

{

    int res,flag,max;

    while (~scanf("%s",str))

     {

        max=;

        n=strlen(str);

        for (int i=;i<n;i++)a[i]=(int)str[i];

        a[n]=;

        for (int i=;i<n;i++)a[i+n+]=int(str[n-i-]);

        a[*n+]=;

        da(a,sa,n*+,);

        calheight(a,sa,*n+);

        RMQ();

        for (int i=;i<n;i++)

         {

            res=lcp(i,*n-i)*-;

            if (max<res)

             {

                max=res;

                flag=i;

             }

            if (i>)

             {

                res=lcp(i,*n-i+)*;

                if (max<res)

                 {

                    max=res;

                    flag=i;

                 }

             }

         }

        if (max%==)

         for (int i=flag-max/;i<=flag+max/;i++)printf("%c",str[i]);

        else

         for (int i=flag-max/;i<=flag+max/-;i++)printf("%c",str[i]);

        puts("");

     }

    return ;

}