求一个串的最大回文字串。
可以用后缀数组解决。
分别考虑奇数和偶数回文子串的情况，枚举原串S的每个位置i作为中间位置看其能向左右两边同时拓展都哪儿：把原串S反转成S'，拼接SaS'（a为一个特殊字符），最远拓展的地方便可以通过LCP(suffix[i],suffix[i'])求得，i'为i对应在S‘的位置。
另外题目要求第一个出现的最长回文串，从左到右枚举中间位置得到的肯定就是出现最早的。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 #define MAXN 2222 7 8 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN]; 9 int cmp(int *r,int a,int b,int l){ 10 return r[a]==r[b] && r[a+l]==r[b+l]; 11 } 12 int sa[MAXN],rank[MAXN],height[MAXN]; 13 void SA(int *r,int n,int m){ 14 int *x=wa,*y=wb; 15 16 for(int i=0; i<m; ++i) ws[i]=0; 17 for(int i=0; i<n; ++i) ++ws[x[i]=r[i]]; 18 for(int i=1; i<m; ++i) ws[i]+=ws[i-1]; 19 for(int i=n-1; i>=0; --i) sa[--ws[x[i]]]=i; 20 21 int p=1; 22 for(int j=1; p<n; j<<=1,m=p){ 23 p=0; 24 for(int i=n-j; i<n; ++i) y[p++]=i; 25 for(int i=0; i<n; ++i) if(sa[i]>=j) y[p++]=sa[i]-j; 26 for(int i=0; i<n; ++i) wv[i]=x[y[i]]; 27 for(int i=0; i<m; ++i) ws[i]=0; 28 for(int i=0; i<n; ++i) ++ws[wv[i]]; 29 for(int i=1; i<m; ++i) ws[i]+=ws[i-1]; 30 for(int i=n-1; i>=0; --i) sa[--ws[wv[i]]]=y[i]; 31 swap(x,y); x[sa[0]]=0; p=1; 32 for(int i=1; i<n; ++i) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 33 } 34 35 for(int i=1; i<n; ++i) rank[sa[i]]=i; 36 int k=0; 37 for(int i=0; i<n-1; height[rank[i++]]=k){ 38 if(k) --k; 39 for(int j=sa[rank[i]-1]; r[i+k]==r[j+k]; ++k); 40 } 41 } 42 43 int st[12][MAXN]; 44 void ST(int *a,int n){ 45 for(int i=1; i<=n; ++i) st[0][i]=a[i]; 46 for(int i=1; i<12; ++i){ 47 for(int j=1; j<=n; ++j){ 48 if(j+(1<<i)>n) break; 49 st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]); 50 } 51 } 52 } 53 int rmq(int a,int b){ 54 if(a>b) swap(a,b); 55 ++a; 56 int k=(int)(log2(b-a+1)+1e-6); 57 return min(st[k][a],st[k][b-(1<<k)+1]); 58 } 59 60 char str[MAXN]; 61 int r[MAXN]; 62 int main(){ 63 scanf("%s",str); 64 int n=strlen(str); 65 for(int i=0; i<n; ++i) r[i]=str[i]; 66 r[n]=1; 67 for(int i=n-1; i>=0; --i) r[n+n-i]=str[i]; 68 r[n<<1|1]=0; 69 SA(r,(n<<1|1)+1,128); 70 ST(height,n<<1|1); 71 int res=0; 72 int posi,flag; 73 for(int i=0; i<n; ++i){ 74 if(res<(rmq(rank[i],rank[n+n-i])-1<<1)+1){ 75 res=(rmq(rank[i],rank[n+n-i])-1<<1)+1; 76 posi=i; flag=0; 77 } 78 if(i && res<(rmq(rank[i],rank[n+n-i+1])<<1)){ 79 res=(rmq(rank[i],rank[n+n-i+1])<<1); 80 posi=i; flag=1; 81 } 82 } 83 if(flag){ 84 for(int i=(res>>1); i>=1; --i) putchar(str[posi-i]); 85 for(int i=0; i<(res>>1); ++i) putchar(str[posi+i]); 86 }else{ 87 for(int i=(res>>1); i>=1; --i) putchar(str[posi-i]); 88 putchar(str[posi]); 89 for(int i=1; i<=(res>>1); ++i) putchar(str[posi+i]); 90 } 91 return 0; 92 }