【题目链接】
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)时间内求解。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int maxn = +;
const int maxd = ; int s[maxn];
int sa[maxn],c[maxn],t[maxn],t2[maxn]; void build_sa(int m,int n) {
int i,*x=t,*y=t2;
for(i=;i<m;i++) c[i]=;
for(i=;i<n;i++) c[x[i]=s[i]]++;
for(i=;i<m;i++) c[i]+=c[i-];
for(i=n-;i>=;i--) sa[--c[x[i]]]=i; for(int k=;k<=n;k<<=) {
int p=;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; for(i=;i<m;i++) c[i]=;
for(i=;i<n;i++) c[x[y[i]]]++;
for(i=;i<m;i++) c[i]+=c[i-];
for(i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y);
p=; x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-]] && y[sa[i]+k]==y[sa[i-]+k]?p-:p++;
if(p>=n) break;
m=p;
}
}
int rank[maxn],height[maxn];
void getHeight(int n) {
int i,j,k=;
for(i=;i<=n;i++) rank[sa[i]]=i;
for(i=;i<n;i++) {
if(k) k--;
j=sa[rank[i]-];
while(s[j+k]==s[i+k]) k++;
height[rank[i]]=k;
}
}
int A[maxn][maxd];
void RMQ_init(int n) {
for(int i=;i<=n;i++) A[i-][]=height[i];
for(int k=;(<<k)<=n;k++)
for(int i=;(i+(<<k))<=n;i++)
A[i][k]=min(A[i][k-],A[i+(<<(k-))][k-]);
}
int query(int l,int r) {
int k=;
while(<<(k+)<=(r-l+)) k++;
return min(A[l][k],A[r-(<<k)+][k]);
}
int lcp(int a,int b) {
int l=rank[a],r=rank[b];
if(r<l) swap(l,r); l--,r--;
if(r<) return ;
return query(l+,r); //l+1
} int n;
char expr[maxn]; int main() {
while(scanf("%s",expr)==) {
int len=strlen(expr),n=*len+;
for(int i=;i<len;i++)s[i]=expr[i];
s[len]=;
for(int i=;i<len;i++)s[i+len+]=expr[len--i];
s[n]=; build_sa('z'+,n+);
getHeight(n);
RMQ_init(n);
int ans=,front,tmp;
for(int i=;i<n;i++) {
tmp=lcp(i,n-i-);
if(*tmp->ans) { //对称个数为奇数
ans=*tmp-;
front=i-tmp+;
}
tmp=lcp(i,n-i);
if(*tmp>ans) { //对称个数为偶数
ans=*tmp;
front=i-tmp;
}
}
expr[front+ans]='\0';
printf("%s\n",expr+front);
}
return ;
}
UPD:16/4/15
【思路】
马拉车（Manacher）裸题辣 :)
不过后缀数组的做法真是神
【代码】
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
#define rep(a,b,c) for(int a=(b);a>=(c);a--)
using namespace std; typedef long long ll;
const int N = 6e3+; char s[N],a[N];
int p[N],ansl,ansr,ans; void Add(int l,int r)
{
l=l/+,r=r/-;
if(l>r) return ;
if(r-l+>ans) {
ans=r-l+;
ansl=l,ansr=r;
}
} void Manacher()
{
int n=strlen(s+);
int m=*n+;
FOR(i,,n) {
a[i<<]=s[i];
a[i<<|]='#';
}
a[]='+',a[]='#',a[m+]='-';
int mx=,id;
FOR(i,,m) {
if(mx>i) p[i]=min(mx-i,p[*id-i]);
else p[i]=;
while(a[i-p[i]]==a[i+p[i]]) p[i]++;
Add(i-p[i],i+p[i]);
if(p[i]+i>mx) mx=i+p[i],id=i;
}
} int main()
{
while(scanf("%s",s+)==) {
ans=ansl=ansr=;
Manacher();
FOR(i,ansl,ansr) putchar(s[i]);
puts("");
}
return ;
}