题目描述：给一个字符串，求最长回文子串，若有多个，输出最先出现的。

注意：题目给的字符串要删去除字母外的其他字符，再进行求解。


题解：设原串为s，在s尾部加一个特殊字符，然后再将s逆序添加在特殊字符的后面。一开始我的思路是直接求最长公共子串，然后出现了反例。abefba，求解是ab，但正确答案是a，错误在于忽略了位置是否对应。正解应该是，从头开始枚举s中的字符s[i]，作为回文串的中间位置，分两种情况。一是回文串长度为奇数，求解rank[i]+1到rank[len-i-1]之间的最小值，作为回文串的长度；二是回文串长度为偶数，求解rank[i]+1到rank[len-i]之间的最小值，作为回文串的长度。求最小值用到的数据结构是ST表。


代码：

#include<bits/stdc++.h>
#define N 2010
using namespace std;

char s[N];
int sa[N],t[N],t2[N],c[N],n,rak[N],height[N];int f[N][13]={0};

void build_sa(int m,char *s)
{
    int i,*x=t,*y=t2;
    for (i=0;i<m;i++)c[i]=0;
    for (i=0;i<n;i++)c[x[i]=s[i]]++;
    for (i=1;i<m;i++)c[i]+=c[i-1];
    for (i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for (int k=1;k<=n;k<<=1)
    {
        int p=0;
        for (i=n-k;i<n;i++)y[p++]=i;
        for (i=0;i<n;i++)if (sa[i]>=k)y[p++]=sa[i]-k;
        for (i=0;i<m;i++)c[i]=0;
        for (i=0;i<n;i++)c[x[y[i]]]++;
        for (i=0;i<m;i++)c[i]+=c[i-1];
        for (i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1; x[sa[0]]=0;
        for (i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if (p>=n) break;
        m=p;
    }
}

void getheight()
{
    int i,j,k=0;
    for (i=0;i<n;i++)rak[sa[i]]=i;
    for (i=0;i<n;i++)
    {
        if (k)k--;
        if (!rak[i])continue;
        j=sa[rak[i]-1];
        while (s[i+k]==s[j+k])k++;
        height[rak[i]]=k;
    }
}

int LCP(int l,int r)
{
    if (l==r)return height[r];
    int k=(int) log2(r-l);
    return min(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{

    scanf("%s",s);
    int i=0,j=0,mid,ans=0,r;n=strlen(s);
    while (!('a'<=s[i]&& s[i]<='z' || 'A'<=s[i]&& s[i]<='Z')) i++;
    for (;i<n;i++) if ('a'<=s[i]&& s[i]<='z' || 'A'<=s[i]&& s[i]<='Z') s[j++]=s[i];
    n=j;
    s[n]='$'; mid=n;
    for (int i=n+1;i<=2*n;i++) s[i]=s[2*n-i]; n=2*n+1;
    
    build_sa(300,s);
    getheight();
    
    for (int i=0;i<n;i++) f[i][0]=height[i];                //建ST表
    for (int k=1;(1<<k)<n;k++)
        for (int i=0;i<n;i++) if (i+(1<<k-1)<n)
                f[i][k]=min(f[i][k-1],f[i+(1<<k-1)][k-1]);

    for (int i=0;i<mid;i++)               //枚举中间位置
    {
        int x=rak[i],y=rak[n-i-1];
        if (x>y)swap(x,y);
        int t=LCP(x+1,y);
        if (2*t-1>ans)                    //长度为奇数
        {
            ans=2*t-1;
            r=i-t+1;
        }
        x=rak[i],y=rak[n-i];
        if (x>y)swap(x,y);
        t=LCP(x+1,y);
        if (2*t>ans)                     //长度为偶数
        {
            ans=t*2;
            r=i-t;
        }
    }
    for (int i=0;i<ans;i++)printf("%c",s[r+i]);puts("");
    return 0;
}