ural 1297 后缀数组求最长回文串

Sample Input

ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA

ArozaupalanalapuazorA

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

解题思路：将字符串反转添加到后面，中间用一个字符隔开，然后枚举，求两个后缀的最长公共前缀。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-1-28 10:15:15
File Name :\acm\代码\4.cpp
************************************************ */

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=10000;
int rank[maxn],sa[maxn],c[maxn],t1[maxn],t2[maxn],height[maxn];
char str[maxn];
int ss[maxn];
void da(int *str,int n,int m)
{
      int i,j,k,p,*x=t1,*y=t2;
      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(k=1;k<=n;k<<=1)
      {
	     p=0;
	     for(i=n-k;i<n;i++)y[p++]=i;
	     for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
	     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];
	     swap(x,y);
	     p=1;
	     x[sa[0]]=0;
	     for(i=1;i<n;i++)
		    x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
	     if(p>=n)break;
	     m=p;
      }
}
void calheight(int *str,int n)
{
      int i,j,k=0;
      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 Log[maxn],best[20][maxn];
void init(int n)
{
      int i,j;
      Log[0]=-1;
      for( i=1;i<=n;i++)
	    Log[i]=(i&(i-1))?Log[i-1]:Log[i-1]+1;
      //cout<<"Log:";for(i=0;i<=n;i++)cout<<Log[i]<<" ";cout<<endl;
      for(i=1;i<=n;i++)best[0][i]=height[i];
      for(i=1;i<=Log[n];i++)
	     for(j=1;j+(1<<i)-1<=n;j++)
		    best[i][j]=min(best[i-1][j],best[i-1][j+(1<<(i-1))]);
}
int lcp(int a,int b)
{
      a=rank[a];
      b=rank[b];
      if(a>b)swap(a,b);
      a++;
      int t=Log[b-a+1];
      return min(best[t][a],best[t][b-(1<<t)+1]);
}
int main()
{
      freopen("data.in","r",stdin);
      freopen("data.out","w",stdout);
      int i,j,k,m,n;
      while(~scanf("%s",str))
      {
	     n=strlen(str);
	    // cout<<"n="<<n<<endl;
	     int len=0;
	     for(i=0;i<n;i++)ss[len++]=str[i];
	     ss[len++]=1;
	     for(i=n-1;i>=0;i--)ss[len++]=str[i];
	     ss[len]=0;
	     da(ss,len+1,300);
	     calheight(ss,len);
         //cout<<"sa:";for(i=0;i<=len;i++)cout<<sa[i]<<" ";cout<<endl;      
         //cout<<"rank:";for(i=0;i<=len;i++)cout<<rank[i]<<" ";cout<<endl;      
         //cout<<"height:";for(i=0;i<=len;i++)cout<<height[i]<<" ";cout<<endl;      
	     
	     init(len);
	   //  cout<<"hahha"<<endl;
	     int ans=0,w;
	     for(i=0;i<n;i++)
	     {
		    j=lcp(i,len-i);
		    if(ans<2*j)ans=2*j,w=i-j;
		    j=lcp(i,len-i-1);
		    if(ans<2*j-1)ans=2*j-1,w=i-j+1;
  	     }
	     str[ans+w]=0;
	     printf("%s\n",str+w);
	    // cout<<ans<<" "<<w<<endl;
	   // while(cin>>i>>j)cout<<lcp(i,j)<<endl;
      }
      return 0;
}




 

ural 1297 后缀数组求最长回文串

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18843245