input | output |
---|---|
ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA |
ArozaupalanalapuazorA |
题目大意:
给你一个字符串,求出其中最长回文串。
首先将这个字符串后加一个‘0’在把这个字符串反向再存一遍。
然后对于以每一个点为中心的回文串,我们分两种情况:
长度为奇数,求i,n-i-1的最长公共前缀。
长度为偶数,求i,n-i的最长公共前缀。(简称lcp)
不断枚举中心点,比较答案即可。
至于求lcp,我们只需要先求出后缀数组中的h数组,做成st表查找rk[i],rk[j]中的最小值即可。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2005; char sr[N]; int sa[N],wa[N<<1],wb[N<<1],to[N],f[13][N]; int ask(int l,int r) { int k=0; for(;1<<(k+1)<=r-l+1;++k); return min(f[k][l],f[k][r-(1<<k)+1]); } int main() { scanf("%s",sr); int l=strlen(sr),n=2*l+1,m=128,*x=wa,*y=wb,mx=0,wz; sr[l]=‘0‘; for(int i=l+1;i<n;++i) sr[i]=sr[2*l-i]; for(int i=0;i<n;++i) ++to[x[i]=sr[i]]; for(int i=1;i<m;++i) to[i]+=to[i-1]; for(int i=n-1;i>=0;--i) sa[--to[x[i]]]=i; for(int j=1,p=0;p<n;m=p,j<<=1) { p=0; for(int i=n-j;i<n;++i) y[p++]=i,x[i+j]=-1;; for(int i=0;p<n;++i) if(sa[i]>=j) y[p++]=sa[i]-j; for(int i=0;i<m;++i) to[i]=0; for(int i=0;i<n;++i) ++to[x[y[i]]]; for(int i=1;i<m;++i) to[i]+=to[i-1]; for(int i=n-1;i>=0;--i) sa[--to[x[y[i]]]]=y[i]; int *t=x;x=y;y=t; x[sa[0]]=0; for(int i=p=1;i<n;++i) y[sa[i]]!=y[sa[i-1]]||y[sa[i]+j]!=y[sa[i-1]+j]?x[sa[i]]=p++:x[sa[i]]=p-1; } for(int i=0,j,k=0;i<n;f[0][x[i++]]=k) if(!x[i]) k=0; else for(k?--k:0,j=sa[x[i]-1];i+k<n&&j+k<n&&sr[i+k]==sr[j+k];++k); for(int i=1;(1<<i)<=n;++i) for(int j=1;j+(1<<i)-1<=n;++j) f[i][j]=min(f[i-1][j],f[i-1][j+(1<<i-1)]); for(int i=0;i<l;++i) { int l=x[i],r=x[n-i-1]; if(l>r) swap(l,r); int t=ask(l+1,r)*2-1; if(t>mx) mx=t,wz=i; if(i) { l=x[i];r=x[n-i]; if(l>r) swap(l,r); t=ask(l+1,r)*2; if(t>mx) mx=t,wz=i; } } for(int i=wz-mx/2;i<=wz+mx/2-!(mx&1);++i) printf("%c",sr[i]); return 0; }
原文:http://www.cnblogs.com/bzmd/p/6391212.html