Ural 1297 Palindrome(后缀数组+最长回文子串)

https://vjudge.net/problem/URAL-1297

题意:

求最长回文子串。

思路:

先将整个字符串反过来写在原字符串后面,中间需要用特殊字符隔开,那么只需要某两个后缀的最长公共前缀。当然,这两个后缀不是让你随便选的,我们需要先确定回文串的中心(那么这儿就需要注意一下奇偶数的情况了,具体可以看一下代码),确定了中心之后,在后面的逆串中,我们也要找到这个中心点的位置,要求的是这两个后缀的公共前缀。

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn=+; int n;
char s[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn];
int Rank[maxn],height[maxn];
int d[maxn][]; void build_sa(int m)
{
int *x=t,*y=t2;
//基数排序
for(int i=;i<m;i++) c[i]=;
for(int i=;i<n;i++) c[x[i]=s[i]]++;
for(int i=;i<m;i++) c[i]+=c[i-];
for(int i=n-;i>=;i--) sa[--c[x[i]]]=i;
for(int k=;k<=n;k<<=)
{
int p=;
//直接利用sa数组排序第二关键字
for(int i=n-k;i<n;i++) y[p++]=i;
for(int i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
//基数排序第一关键字
for(int i=;i<m;i++) c[i]=;
for(int i=;i<n;i++) c[x[y[i]]]++;
for(int i=;i<m;i++) c[i]+=c[i-];
for(int i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];
//根据sa和y计算新的x数组
swap(x,y);
p=;
x[sa[]]=;
for(int 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; //下次基数排序的最大值
}
} 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--;
int j=sa[Rank[i]-];
while(s[i+k]==s[j+k]) k++;
height[Rank[i]]=k;
}
} void RMQ(int n)
{
for(int i=;i<=n;i++) d[i-][]=height[i];
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<n;i++)
d[i][j]=min(d[i][j-],d[i+(<<(j-))][j-]);
} int query(int L, int R)
{
int k=;
while((<<(k+))<=R-L+) k++;
return min(d[L][k],d[R-(<<k)+][k]);
} int LCP(int a, int b)
{
int x=Rank[a],y=Rank[b];
if(x>y) swap(x,y);
x--; y--;
if(y<) return ;
return query(x+,y);
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%s",s))
{
int len = strlen(s);
s[len]='';
for(int i=;i<len;i++) s[i+len+]=s[len--i];
s[*len+]=''; //这儿后面的数要加的不一样,一开始两个都加了'0'...
n=*len+;
build_sa();
getHeight(n-);
RMQ(n-);
int ans=, tmp, start;
for(int i=;i<len;i++)
{
tmp=LCP(i,n-i-); //长度为奇数的情况
if(*tmp->ans)
{
ans=*tmp-;
start=i-tmp+;
}
tmp=LCP(i,n-i-); //长度为偶数的情况
if(*tmp>ans)
{
ans=*tmp;
start=i-tmp;
}
}
for(int i=start;i<start+ans;i++)
printf("%c",s[i]);
printf("\n");
}
return ;
}
上一篇:看完你也能独立负责项目!产品经理做APP从头到尾的所有工作流程详解!


下一篇:华为章宇:如何学习开源项目及Ceph的浅析