ural 1297 Palindrome （后缀数组最长回文）

你的名字 2022-08-24 05:27 62阅读 0赞

题意：给定一个字符串，求最长回文子串。

以下分析部分摘自 [后缀数组两种算法的分析比较 - Localhost 8080 - C++博客][- Localhost 8080 - C]

穷举每一位，然后计算以这个字符为中心的最长回文子串。注意这里要分两种情况，一是回文子串的长度为奇数，二是长度为偶数。两种情况都可以转化为求一个后缀和一个反过来写的后缀的最长公共前缀。具体的做法是：将整个字符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变为了求这个新的字符串的某两个后缀的最长公共前缀。如图6所示。

![3b6573eed0dd97d4ce1b3ea9.JPG][]

这个做法的时间复杂度为O(nlogn)。如果RMQ问题用时间为O(n)的方法预处理，那么本题的时间复杂度可以降为O(n)。

做这个题的时候发现 rank 是c++库函数中定义的一个结构体。。。如果用using namespace std; 在ural上会ce

![Image 1][]

别的OJ貌似没有这个问题

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N = int(2e3)+10;
    
    int cmp(int *r,int a,int b,int l){
    	return (r[a]==r[b]) && (r[a+l]==r[b+l]);
    }
    int wa[N],wb[N],ws[N],wv[N];
    int rank[N],height[N],sa[N];
    
    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++) ws[i]=0;
    	for(i=0;i<n;i++) ws[x[i]=r[i]]++;
    	for(i=1;i<m;i++) ws[i]+=ws[i-1];
    	for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
    	for(j=1,p=1;p<n;j*=2,m=p){
    		for(p=0,i=n-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++) ws[i]=0;
    		for(i=0;i<n;i++) ws[wv[i]]++;
    		for(i=1;i<m;i++) ws[i]+=ws[i-1];
    		for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
    		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
    			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    		//printf("p = %d\n", p );
    	}
    }
    void calheight(int *r,int *sa,int n){
    //	memset(height,0,sizeof(height));
    //	memset(rank,0,sizeof(rank));
    	int i,j,k=0;
    	for(i=1;i<=n;i++) rank[sa[i]]=i;
    	for(i=0;i<n; height[rank[i++]] = k )
    	for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
    }
    
    char str[N];
    int Log[N],data[N];
    int best[20][N];
    
    void initRMQ (int n){//初始化RMQ
    	int i;
    	Log[0] = -1;
    	for (i=1;i<=n;i++)
            Log[i]=(i&(i-1))?Log[i-1]:Log[i-1]+1;
    	for (i=1;i<=n;i++) best[0][i]=height[i];
    	for (i=1;i<=Log[n];i++){
    		int limit=n-(1<<i)+1;
    		for (int j=1;j<=limit;j++)
    			best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]);
    	}
    }
    int lcp (int a,int b){//询问a,b后缀的最长公共前缀
    	a=rank[a]; b=rank[b];
    	if (a>b) std::swap(a,b);
    	a++;
    	int t=Log[b-a+1];
    	return min(best[t][a] , best[t][b - (1<<t) + 1]);
    }
    
    void Deal (int len,int n)
    {
    	int start,ans=1,tmp,i;
    	for (i=0;i<len;i++)
    	{
    		tmp=lcp(i,n-i-1);  //回文长度是奇数的情况
    		if (tmp*2-1>ans)
    		{
    			ans=tmp*2-1;
    			start=i-tmp+1;
    		}
    		tmp=lcp(i,n-i);    //回文长度是偶数的情况
    		if (tmp*2>ans)
    		{
    			ans=tmp*2;
    			start=i-tmp;
    		}
    	}
    	if (ans==1) printf("%c\n",str[0]);
    	else
    	{
    		for (i=start;i<start+ans;i++)
    			printf("%c",str[i]);
    		printf("\n");
    	}
    }
    
    int main ()
    {
    	int i,n=0;
    	scanf("%s",str);
    	int len=strlen(str);
    	for (i=0;i<len;i++)
    		data[n++]=str[i];
    	data[n++]=126;
    	for (i=len-1;i>=0;i--)
    		data[n++]=str[i];
    	data[n]=0;
    	DA(data,sa,n+1,130);
    	calheight(data,sa,n);
    	initRMQ(n);
    	Deal (len,n);
    	return 0;
    }

[- Localhost 8080 - C]: http://www.cppblog.com/superKiki/archive/2010/05/15/115421.html
[3b6573eed0dd97d4ce1b3ea9.JPG]: /images/20220823/5ae229a588b4473286f13394060be8d9.png
[Image 1]: