2018.12.17-dtoj-1167-最长回文子串

题目描述：

给定一个字符串，求最长回文子串。

回文子串：如果将字符串L的某个子字符串R反过来写后和原来的字符串R 一样，则称字符串R是字符串L的回文子串。

算法标签：sa

以下代码：

#include<bits/stdc++.h>
#define il inline
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=2e5+9;char s[N];
int n,l,rk[N],sa[N],height[N],x[N],y[N],mn[N][20],c[N],ans=1,pos=1;
il int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}
il void getsa(){
  int m=128;
  for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
  for(int i=2;i<=m;i++)c[i]+=c[i-1];
  for(int i=n;i;i--)sa[c[x[i]]--]=i;
  for(int k=1;k<=n;k<<=1){
    int num=0;
    for(int i=n-k+1;i<=n;i++)y[++num]=i;
    for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
    for(int i=1;i<=m;i++)c[i]=0;
    for(int i=1;i<=n;i++)c[x[i]]++;
    for(int i=2;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
    swap(x,y);x[sa[1]]=1;num=1;
    for(int i=2;i<=n;i++)
      x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
    if(num==n)break;m=num;
  }
  for(int i=1;i<=n;i++)rk[sa[i]]=i;
}
il void geth(){
  int k=0;
  for(int i=1;i<=n;i++){
    if(rk[i]==1)continue;
    if(k)k--;int j=sa[rk[i]-1];
    while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
    height[rk[i]]=k;
  }
}
il int rmq(int l,int r){
  int k=0;while((1<<(k+1))<=r-l+1)k++;
  return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
il void init(){
  for(int i=1;i<=n;i++)mn[i][0]=height[i];
  for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)
    mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
il int Lcp(int x,int y){
  int l=rk[x],r=rk[y];if(l>r)swap(l,r);return rmq(l+1,r);
}
int main()
{
  scanf(" %s",s+1);n=l=strlen(s+1);s[++n]='#';
  for(int i=l;i;i--)s[++n]=s[i];s[++n]='$';
  getsa();geth();init();
  for(int i=1;i<=l;i++){
    int lcp=Lcp(i,n-i);
    if(lcp*2-1>ans||(lcp*2-1==ans&&i-lcp+1<pos))pos=i-lcp+1,ans=lcp*2-1;
    lcp=Lcp(i,n-i+1);
    if(lcp*2>ans||(lcp*2==ans&&i-lcp<pos))ans=lcp*2,pos=i-lcp;
  }
  for(int i=pos;i<pos+ans;i++)printf("%c",s[i]);
  return 0;
}