考虑奇数长度的回文，对于字符串上的每个位置i，如果知道从i开始的后缀和到i为止的前缀反转后的字符串的lcp长度的话，也就知道了以第i个字符为对称中心的最长回文的长度了。因此，我们用在S中不会出现的字符将S和S反转后的字符串拼接起来，得到字符串S'，计算S'的sa。于是，从i开始的后缀和到i为止的前缀反转后的字符串就都是S'中的后缀了，利用高度数组，可以轻易地求得它们最长公共前缀的长度。

对于长度为偶数的回文的处理也基本相同。

哈哈哈，MLE+TLE不可避。

#include
     
      #include
      
       #include
       
        using namespace std;#define N 2000001#define INF 2147483647char s[N];int tong['z'+1],t[N],n,t2[N],sa[N],lcp[N],rank[N];bool cmp(int *y,int i,int k){	return ((y[sa[i-1]]==y[sa[i]])&&((sa[i-1]+k>=n?-1:y[sa[i-1]+k])==(sa[i]+k>=n?-1:y[sa[i]+k])));}void build_sa(int range){	int *x=t,*y=t2;	memset(tong,0,sizeof(int)*range);	for(int i=0;i
        
         =0;--i) sa[--tong[x[i]]]=i;	for(int k=1;k<=n;k<<=1)	  {	  	int p=0;	  	for(int i=n-k;i
         
          =k) y[p++]=sa[i]-k;	  	memset(tong,0,sizeof(int)*range);		for(int i=0;i
          
           =0;--i) sa[--tong[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for(int i=1;i
           
            =n) break; range=p; }}void get_lcp(){ int k=0; for(int i=0;i
            
             >1); buildtree(rt<<1,l,m); buildtree(rt<<1|1,m+1,r); minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);}int query(int ql,int qr,int rt,int l,int r){ if(ql<=l&&r<=qr) return minv[rt]; int m=(l+r>>1),res=INF; if(ql<=m) res=min(res,query(ql,qr,rt<<1,l,m)); if(m