ural1297 求最长回文子串 | 后缀数组

#include<cstdio>

#include<algorithm>

#include<cstring>

#define N 20005

using namespace std;

int buf1[N],buf2[N],sa[N],rnk[N],buc[N],n,height[N],ans,Log[N],pos,Min[N][];

char s[N];

void suffix_sort()

{

    int *x=buf1,*y=buf2,m=;

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

    for (int i=;i<=n;i++) buc[x[i]=s[i]]++;

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

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

    for (int k=;k<=n;k<<=)

    {

        int  p=;

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

            y[++p]=i;

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

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

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

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

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

        for (int i=n;i;i--) sa[buc[x[y[i]]]--]=y[i];

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

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

            if (y[sa[i-]]==y[sa[i]] && y[sa[i-]+k]== y[sa[i]+k])

                x[sa[i]]=p;

             else x[sa[i]]=++p;

        if ((m=p)>=n) break;

    }

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

    rnk[sa[i]]=i;

    for (int i=,j,k=;i<=n;i++)

    {

        if (rnk[i]==) continue;

        if (k) k--;

        j=sa[rnk[i]-];

        while (s[i+k]==s[j+k] && i+k<=n && j+k<=n) k++;

        height[rnk[i]]=k;

    }

}

void InitRmq()

{

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

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

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

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

}

int Query(int x,int y)

{

    int i=rnk[x],j=rnk[y];

    if (i>j) swap(i,j);

    int len=Log[j-i];

    return min(Min[i+][len],Min[j-(<<len)+][len]);

}

int main()

{

    scanf("%s",s+);

    n=strlen(s+);

    if (n==)

    {

    puts(s+);

    return ;

    }

    s[n+]='#';

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

    s[*n+-i]=s[i];

    n=n*+;

    suffix_sort();

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

    Log[i]=Log[i>>]+;

    InitRmq();

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

    {

    int tmp=Query(i,n-i+);

    if (tmp*>ans) ans=tmp*,pos=i-tmp;

    tmp=Query(i,n-i+);

    if (tmp*->ans) ans=tmp*-,pos=i-tmp+;

    }

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

    putchar(s[i+pos-]);

    return ;

}