【题目链接】 

 

【题目大意】

　　给出一个字符串，要求在其后面添加最少的字符数，使得其成为一个回文串。并输出这个回文串。

 

【题解】

　　用拼接符将原字符串倒序相接，做一遍后缀数组，查询两串相应位置的LCP就是以该点为中心的回文串长度的一半分，奇偶求出所有后缀回文串，保留最长的，则补充部分为剩下的前缀的倒置。至于查询两串的LCP我们可以在height数组建立ST表查询。

 

【代码】

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N=4000010;int n,m,Rank[N],sa[N],h[N],tmp[N],cnt[N],ans;char s[N],t[N];void suffixarray(int n,int m){    int i,j,k;n++;    for(i=0;i<2*n+5;i++)Rank[i]=sa[i]=h[i]=tmp[i]=0;    for(i=0;i
        
         =n-1)break;    }for(j=Rank[h[i=k=0]=0];i
         
          r)swap(l,r);l++;      int k=lg2[r-l+1];      return min(f[l][k],f[r-(1<
          
           =0;i++,j--)s[i]=t[j]; s[m=i]=0;}int main(){ while(~scanf("%s",t)){ init(); suffixarray(m,128); rmq_init(m); int ans=0,pos=m+1; for(int i=0;i
           
            ans&&i+k==n)ans=2*k-1,pos=i-k+1; k=rmq_min(Rank[i],Rank[m-i]); if(2*k>ans&&i+k==n)ans=2*k,pos=i-k; }for(int i=0;i
            
             =0;i--)printf("%c",s[i]); puts(""); }return 0;}