把一份倒序复制到后面
中间加上阻断符号（为了防止两边超过自己范围），然后枚举中间点（分奇数偶数讨论）
代码：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
#define maxn 1000010
int x[maxn],y[maxn],sa[maxn],height[maxn],
rank[maxn],c[maxn],a[maxn],h,t;
char s[maxn];
int n,m,bz[28][500000];
void asa(int n,int m)
{
int p=0,f=0;
for (int i=1;i<=m;i++) c[i]=0;
for (int i=1;i<=n;i++) c[x[i]=a[i]]++;
for (int i=1;i<=m;i++) c[i]+=c[i-1];
for (int i=n;i;i--) sa[c[x[i]]--]=i;
for(int i=1;i<=n&&p<=n;i<<=1)
{
p=0;
for (int j=n-i+1;j<=n;j++) y[++p]=j;
for (int j=1;j<=n;j++)
if (sa[j]>i) y[++p]=sa[j]-i;
for (int j=1;j<=m;j++) c[j]=0;
for (int j=1;j<=n;j++) c[x[y[j]]]++;
for (int j=1;j<=m;j++) c[j]+=c[j-1];
for (int j=n;j;j--) sa[c[x[y[j]]]--]=y[j];
swap(x,y); x[sa[1]]=1; p=2;
for (int j=2;j<=n;j++)
x[sa[j]]=y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i]
?p-1:p++;
m=p;
}
for (int i=1;i<=n;i++) rank[sa[i]]=i;
for (int i=1;i<=n;i++)
{
int j=sa[rank[i]-1];
if (f) f--;
while (a[i+f]==a[j+f]) f++;
height[rank[i]]=f;
}
}
int lcp(int a,int b)
{
int x=rank[a],y=rank[b];
if (x>y) swap(x,y); x++;
int z=log2(y-x+1);
return(min(bz[z][x],bz[z][y-(1<<z)+1]));
}
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
cin>>s;
n=strlen(s);
for (int i=1;i<=n;i++)
a[i]=a[2*n-i+2]=s[i-1]-' ';
a[n+1]='$'-' ';
asa(2*n+1,200);
for (int i=1;i<=2*n+1;i++)
bz[0][i]=height[i];
for (int i=1;i<=25;i++)
for (int j=1;j<=2*n+1;j++)
// for (int j=1;j+(1<<i)-1<=2*n+1;j++)
if (j+(1<<i)-1<=2*n+1)
{
bz[i][j]=min(bz[i-1][j],bz[i-1][j+(1<<(i-1))]);
}
/* n=2*n+1;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
bz[j][i]=min(bz[j-1][i] , bz[j-1][i+(1<<(j-1))]);
for (int i=1;i<=2*n+1;i++)
for (int j=0;j<=15;j++) cout<<bz[j][i];*/
int ans=0,pos;
for (int i=1;i<=n;i++)
{
if (2*lcp(i,2*n-i+2)-1>ans)
{
ans=2*lcp(i,2*n-i+2)-1; pos=i;
}
if (2*lcp(i,2*n-i+2+1)>ans)
{
ans=2*lcp(i,2*n-i+2+1); pos=i;
}
}
cout<<ans;//<<s+pos-ans/2<<endl;
// cout<<s[pos-2]<<s[pos-1];
return 0;
}