URAL 1297. Palindrome(输出最长回文子串--后缀数组)
Input
Output
Sample
input | output |
---|---|
ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA |
ArozaupalanalapuazorA |
Problem Source: IX Open Collegiate Programming Contest of the High School Pupils (13.03.2004)
My submissions All submissions (19277) All accepted submissions (5968)
// 1297. Palindrome G++ 4.9 Accepted 0.031 530 KB #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std;; const int MAXN=2010; int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量,不需要赋值 //待排序的字符串放在s数组中,从s[0]到s[n-1],长度为n,且最大值小于m, //除s[n-1]外的所有s[i]都大于0,r[n-1]=0 //函数结束以后结果放在sa数组中 bool cmp(int *r,int a,int b,int l) { return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int str[],int sa[],int rank[],int height[],int n,int m) { n++;//注意 int i, j, p, *x = t1, *y = t2; //第一轮基数排序,如果s的最大值很大,可改为快速排序(只改第一轮) for(i = 0;i < m;i++) c[i] = 0; for(i = 0;i < n;i++) c[x[i] = str[i]]++; for(i = 1;i < m;i++) c[i] += c[i-1]; for(i = n-1;i >= 0;i--) sa[--c[x[i]]] = i; for(j = 1;j <= n; j <<= 1) { p = 0; //直接利用sa数组排序第二关键字 for(i = n-j; i < n; i++) y[p++] = i;//后面的j个数第二关键字为空的最小 for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j; //这样数组y保存的就是按照第二关键字排序的结果 //基数排序第一关键字 for(i = 0; i < m; i++) c[i] = 0; for(i = 0; i < n; i++) c[x[y[i]]]++; for(i = 1; i < m;i++) c[i] += c[i-1]; for(i = n-1; i >= 0;i--) sa[--c[x[y[i]]]] = y[i]; //根据sa和x数组计算新的x数组 swap(x,y);//小优化 p = 1; x[sa[0]] = 0; for(i = 1;i < n;i++) x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++; if(p >= n) break;//小优化 m = p;//下次基数排序的最大值 } int k = 0; n--;//注意 for(i = 0;i <= n;i++) rank[sa[i]] = i; for(i = 0;i < n;i++) { if(k) k--; j = sa[rank[i]-1]; while(str[i+k] == str[j+k]) k++; height[rank[i]] = k; } } int rank[MAXN],height[MAXN]; int RMQ[MAXN]; int mm[MAXN]; int best[20][MAXN]; void initRMQ(int n) { mm[0]=-1; for(int i=1;i<=n;i++) mm[i]= (i&(i-1))==0? mm[i-1]+1 : mm[i-1]; for(int i=1;i<=n;i++) best[0][i]=i; for(int i=1;i<=mm[n];i++) for(int j=1;j+(1<<i)-1<=n;j++) { int a=best[i-1][j]; int b=best[i-1][j+(1<<(i-1))]; if(RMQ[a]<RMQ[b]) best[i][j]=a; else best[i][j]=b; } } int askRMQ(int a,int b) { int t=mm[b-a+1]; b= b-(1<<t)+1; a=best[t][a],b=best[t][b]; return RMQ[a]<RMQ[b]? a:b; } int lcp(int a,int b) { a= rank[a]; b= rank[b]; return height[askRMQ(min(a,b)+1,max(a,b))]; } char str[MAXN]; int r[MAXN]; int sa[MAXN]; int main() { while(~scanf("%s",str)) { int len=strlen(str); int n=len*2+1; for(int i=0;i<len;i++) r[i]=str[i]; r[len]=1; for(int i=0;i<len;i++) r[i+len+1]=str[len-i-1]; r[n]=0; da(r,sa,rank,height,n,130); for(int i=1;i<=n;i++) RMQ[i] = height[i]; initRMQ(n); int st,maxn=-1; for(int i=0;i<len;i++) { int tmp; tmp=lcp(i,n-i); if(maxn<2*tmp) { maxn=2*tmp; st=i-tmp; } tmp=lcp(i,n-i-1); if(maxn<2*tmp-1) { maxn=2*tmp-1; st=i-tmp+1; } } str[st+maxn]=0; printf("%s\n",str+st); } return 0; }
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int MAXN=1010; char Ma[MAXN*2]; int Mp[MAXN*2]; void Manacher(char s[],int len) { int l=0; Ma[l++]='$'; Ma[l++]='#'; for(int i=0;i<len;i++) { Ma[l++] = s[i]; Ma[l++] = '#'; } Ma[l]=0; int mx=0,id=0; for(int i=1;i<l;i++) { Mp[i] = mx>i? min(Mp[2*id-i],mx-i):1; while(Ma[i+Mp[i] ]==Ma[i-Mp[i] ]) Mp[i]++; if(i+Mp[i]>mx) { mx=i+Mp[i]; id=i; } } } char s[MAXN]; int main() { while(~scanf("%s",s)) { int len=strlen(s); Manacher(s,len); int ans=0; int st; for(int i=0;i<2*len+2;i++) if(ans<Mp[i]-1) { ans = Mp[i]-1; st = (i-Mp[i])>>1; } s[st+ans]=0; printf("%s\n",s+st); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。