【题目链接】
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12406
【题意】
求最长回文子串。
【思路】
将字符串反向拼接在后，中间用一个没有出现的字符隔开，则问题转化为求新字符串两个特定后缀的lcp，枚举对称点i，对称数为奇的情况对应求lcp(i,n-i)，对称数为偶的情况对应求lcp(i,n-i-1)。
如图所示：
两个后缀的lcp可以用Sparse Table算法（倍增）在O(nlogn)时间内求解。
【代码】
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define FOR(a,b,c) for(int a=(b);a<=(c);a++) 5 using namespace std; 6 7 const int maxn = 3000+10; 8 const int maxd = 22; 9 10 int s[maxn]; 11 int sa[maxn],c[maxn],t[maxn],t2[maxn]; 12 13 void build_sa(int m,int n) { 14 int i,*x=t,*y=t2; 15 for(i=0;i<m;i++) c[i]=0; 16 for(i=0;i<n;i++) c[x[i]=s[i]]++; 17 for(i=1;i<m;i++) c[i]+=c[i-1]; 18 for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i; 19 20 for(int k=1;k<=n;k<<=1) { 21 int p=0; 22 for(i=n-k;i<n;i++) y[p++]=i; 23 for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; 24 25 for(i=0;i<m;i++) c[i]=0; 26 for(i=0;i<n;i++) c[x[y[i]]]++; 27 for(i=0;i<m;i++) c[i]+=c[i-1]; 28 for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; 29 30 swap(x,y); 31 p=1; x[sa[0]]=0; 32 for(i=1;i<n;i++) 33 x[sa[i]]=y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++; 34 if(p>=n) break; 35 m=p; 36 } 37 } 38 int rank[maxn],height[maxn]; 39 void getHeight(int n) { 40 int i,j,k=0; 41 for(i=0;i<=n;i++) rank[sa[i]]=i; 42 for(i=0;i<n;i++) { 43 if(k) k--; 44 j=sa[rank[i]-1]; 45 while(s[j+k]==s[i+k]) k++; 46 height[rank[i]]=k; 47 } 48 } 49 int A[maxn][maxd]; 50 void RMQ_init(int n) { 51 for(int i=1;i<=n;i++) A[i-1][0]=height[i]; 52 for(int k=1;(1<<k)<=n;k++) 53 for(int i=0;(i+(1<<k))<=n;i++) 54 A[i][k]=min(A[i][k-1],A[i+(1<<(k-1))][k-1]); 55 } 56 int query(int l,int r) { 57 int k=0; 58 while(1<<(k+1)<=(r-l+1)) k++; 59 return min(A[l][k],A[r-(1<<k)+1][k]); 60 } 61 int lcp(int a,int b) { 62 int l=rank[a],r=rank[b]; 63 if(r<l) swap(l,r); l--,r--; 64 if(r<0) return 0; 65 return query(l+1,r); //l+1 66 } 67 68 int n; 69 char expr[maxn]; 70 71 int main() { 72 while(scanf("%s",expr)==1) { 73 int len=strlen(expr),n=2*len+1; 74 for(int i=0;i<len;i++)s[i]=expr[i]; 75 s[len]=1; 76 for(int i=0;i<len;i++)s[i+len+1]=expr[len-1-i]; 77 s[n]=0; 78 79 build_sa('z'+1,n+1); 80 getHeight(n); 81 RMQ_init(n); 82 int ans=0,front,tmp; 83 for(int i=0;i<n;i++) { 84 tmp=lcp(i,n-i-1); 85 if(2*tmp-1>ans) { //对称个数为奇数 86 ans=2*tmp-1; 87 front=i-tmp+1; 88 } 89 tmp=lcp(i,n-i); 90 if(2*tmp>ans) { //对称个数为偶数 91 ans=2*tmp; 92 front=i-tmp; 93 } 94 } 95 expr[front+ans]=' '; 96 printf("%s ",expr+front); 97 } 98 return 0; 99 }
UPD:16/4/15
【思路】
马拉车（Manacher）裸题辣 :)
不过后缀数组的做法真是神
【代码】
1 #include<set> 2 #include<cmath> 3 #include<queue> 4 #include<vector> 5 #include<cstdio> 6 #include<cstring> 7 #include<iostream> 8 #include<algorithm> 9 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt) 10 #define FOR(a,b,c) for(int a=(b);a<=(c);a++) 11 #define rep(a,b,c) for(int a=(b);a>=(c);a--) 12 using namespace std; 13 14 typedef long long ll; 15 const int N = 6e3+10; 16 17 char s[N],a[N]; 18 int p[N],ansl,ansr,ans; 19 20 void Add(int l,int r) 21 { 22 l=l/2+1,r=r/2-1; 23 if(l>r) return ; 24 if(r-l+1>ans) { 25 ans=r-l+1; 26 ansl=l,ansr=r; 27 } 28 } 29 30 void Manacher() 31 { 32 int n=strlen(s+1); 33 int m=2*n+1; 34 FOR(i,1,n) { 35 a[i<<1]=s[i]; 36 a[i<<1|1]='#'; 37 } 38 a[0]='+',a[1]='#',a[m+1]='-'; 39 int mx=0,id; 40 FOR(i,1,m) { 41 if(mx>i) p[i]=min(mx-i,p[2*id-i]); 42 else p[i]=1; 43 while(a[i-p[i]]==a[i+p[i]]) p[i]++; 44 Add(i-p[i],i+p[i]); 45 if(p[i]+i>mx) mx=i+p[i],id=i; 46 } 47 } 48 49 int main() 50 { 51 while(scanf("%s",s+1)==1) { 52 ans=ansl=ansr=0; 53 Manacher(); 54 FOR(i,ansl,ansr) putchar(s[i]); 55 puts(""); 56 } 57 return 0; 58 }