Palindrome https://vjudge.net/problem/URAL-1297
题意:
求给定字符串的最长回文子串.
分析:
首先想到的是求 str 与反序的 str 的最大公共子串, 考虑 abcdba 这种情况, 所以对于求出的公共子串判断一下是否是回文串即可. 还有一种做法是枚举每一个字符为回文串的中间点, 求出这个字符的后缀与前缀的最长公共子串就是回文串. 对于前缀可以认为是反序 str 中对应字符的后缀, 根据后缀树组中 height 数组的性质, suffix(i) 和 suffix(j) 的最长公共前缀为 height[rank[i] +1] ,height[rank[i] +2] ......height[rank[j] ] 中的最小值, 考虑用 ST 表维护一个区间最小值即可.
参考博客: 大佬博客 https://www.cnblogs.com/lidaxin/p/5002878.html
代码:
- #include <map>
- #include <queue>
- #include <math.h>
- #include <string>
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define cls(x) memset(x,0,sizeof(x))
- #define clslow(x) memset(x,-1,sizeof(x))
- const int maxlog=20;
- const int maxn=1e5+100;
- char str[maxn];
- int r[maxn],sa[maxn],Rank[maxn],height[maxn];
- namespace Suffix {
- int wa[maxn],wb[maxn],wv[maxn],wt[maxn];
- int cmp(int *r,int a,int b,int k)
- {
- return r[a]==r[b]&&r[a+k]==r[b+k];
- }
- void da(int *r,int *sa,int n,int m)
- {
- int i,j,p,*x=wa,*y=wb,*t;
- for(i=0; i<m; i++) wt[i]=0;
- for(i=0; i<=n; i++) wt[x[i]=r[i]]++;
- for(i=1; i<m; i++) wt[i]+=wt[i-1];
- for(i=n; i>=0; i--) sa[--wt[x[i]]]=i;
- p=1;
- j=1;
- for(; p<=n; j*=2,m=p)
- {
- for(p=0,i=n+1-j; i<=n; i++) y[p++]=i;
- for(i=0; i<=n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
- for(i=0; i<=n; i++) wv[i]=x[y[i]];
- for(i=0; i<m; i++) wt[i]=0;
- for(i=0; i<=n; i++) wt[wv[i]]++;
- for(i=1; i<m; i++) wt[i]+=wt[i-1];
- for(i=n; i>=0; i--) sa[--wt[wv[i]]]=y[i];
- t=x;
- x=y;
- y=t;
- x[sa[0]]=0;
- for(p=1,i=1; i<=n; i++)
- x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
- }
- }
- void getheight(int *r,int* sa,int n)
- {
- int i,j,k=0;
- for(i=1; i<=n; i++) Rank[sa[i]]=i;
- for(i=0; i<n; i++)
- {
- if(k)
- k--;
- else
- k=0;
- j=sa[Rank[i]-1];
- while(r[i+k]==r[j+k])
- k++;
- height[Rank[i]-1]=k;
- }
- }
- };
- namespace ST{
- int d[maxn][maxlog];
- void init(int n)
- {
- for(int i=1;i<=n;i++) d[i][0]=height[i];
- for(int j=1;(1<<j)<=n;j++){
- for(int i=1;i+(1<<j)<=n;i++){
- d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
- }
- }
- }
- int query(int L,int R)
- {
- int k=0;
- while((1<<(k+1))<=R-L+1) k++;
- return min(d[L][k],d[R-(1<<k)+1][k]);
- }
- };
- int lcp(int a,int b)
- {
- int l=Rank[a],r=Rank[b];
- if(l>r) swap(l,r);
- return ST::query(l,r-1);
- }
- int main()
- {
- // freopen("in.txt","r",stdin);
- while(scanf("%s",str)!=EOF)
- {
- int n=0;
- int slen=strlen(str);
- for(int i=0;i<slen;i++){
- r[n++]=str[i]-'A'+1;
- }
- r[n++]=60;
- for(int i=slen-1;i>=0;i--){
- r[n++]=str[i]-'A'+1;
- }
- r[n]=0;
- Suffix::da(r,sa,n,61);
- Suffix::getheight(r,sa,n);
- ST::init(n);
- int pos,maxlen=0;
- for(int i=0;i<n;i++){
- int reval=lcp(i,n-i-1);
- if(maxlen<2*reval-1){
- pos=i-reval+1;
- maxlen=2*reval-1;
- }
- reval=lcp(i,n-i);
- if(maxlen<2*reval){
- pos=i-reval;
- maxlen=2*reval;
- }
- }
- for(int i=pos;i<pos+maxlen;i++){
- printf("%c",r[i]-1+'A');
- }
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2722749.html