最长回文子串

http://www.nocow.cn/index.php/Translate:USACO/calfflac 题意就是在一个字符串中找到最长的回文串，一般的dp问题有问题（虽然USACO过……）

一、直接模拟法

枚举每个字符为中间字符向两边扩展，但是要注意奇数和偶数的问题，这就可以对原串进行改进，也就是在两边和每个字符间加上‘#’,具体改进方法见方法二

二、算法大致过程是这样。先在每两个相邻字符中间插入一个分隔符，当然这个分隔符要在原串中没有出现过。一般可以用‘#’分隔。这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了（见下面的一个例子，回文串长度全为奇数了），然后用一个辅助数组P记录以每个字符为中心的最长回文串的信息。P［id］记录的是以字符str［id］为中心的最长回文串，当以str［id］为第一个字符，这个最长回文串向右延伸了P［id］个字符。
   原串： w aa bwsw f d
   新串： # w # a # a # b # w # s # w # f # d #
辅助数组P： 1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1
   这里有一个很好的性质，P［id］-1就是该回文子串在原串中的长度（包括‘#’）。如果这里不是特别清楚，可以自己拿出纸来画一画，自己体会体会。当然这里可能每个人写法不尽相同，不过我想大致思路应该是一样的吧。
   好，我们继续。现在的关键问题就在于怎么在O（n）时间复杂度内求出P数组了。只要把这个P数组求出来，最长回文子串就可以直接扫一遍得出来了。
   由于这个算法是线性从前往后扫的。那么当我们准备求P［i］的时候，i以前的P［j］我们是已经得到了的。我们用mx记在i之前的回文串中，延伸至最右端的位置。同时用id这个变量记下取得这个最优mx时的id值。（注：为了防止字符比较的时候越界，我在这个加了‘#’的字符串之前还加了另一个特殊字符‘$’，故我的新串下标是从1开始的）

代码：

void pk()
{
    int i;
    int mx = 0;
    int id;
    for(i=1; i<n; i++)
    {
        if( mx > i )
            p[i] = MIN( p[2*id-i], mx-i );
        else
            p[i] = 1;
        for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
            ;
        if( p[i] + i > mx )
        {
            mx = p[i] + i;
            id = i;
        }
    }
}
三、后缀数组

一个整体O(n)的算法（参考许智磊论文）

整体用后缀数组实现。

求以i为中心向两边扩展的最远值，等价于求Suffix(i)和Suffix(i')的最长公共前缀。其中i'=2n-i+2

解法： 1.初始化答案为0。S=T+'#'+Reverse(T)+$，得到串S （O(n)） 2.求出后缀数组SA、名次数组Rank （倍增法：O(nlogn) Dc3算法：O(n)） 3.计算height数组并进行标准RMQ方法预处理（O(n)） 4.枚举i，计算以i为对称中心的极长回文串并更新答案（O(n)）

代码：

#include<stdio.h>
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
ifstream fin("calfflac.in");
ofstream fout("calfflac.out");

const int MAX=20000*6;
char ab[MAX];
int point[MAX];
int sa[MAX];
int rb[MAX];
int rank[MAX],height[MAX];
int n,m;

int wa[MAX],wb[MAX],wv[MAX],wk[100];
int tb;

int F(int i,int tb)
{
if(i%3==1)
return i/3;
else return i/3+tb;
}

int G(int i,int tb)
{
if(i<tb)
return i*3+1;
else return (i-tb)*3+2;
}

int compare0(int*r,int i,int j)
{
return r[i]==r[j]&&r[i+1]==r[j+1]&&r[i+2]==r[j+2];
}

int compare1(int k,int*r,int i,int j)
{
if(k==2)
{
return r[i]<r[j]||r[i]==r[j]&&compare1(1,r,i+1,j+1);
}else return r[i]<r[j]||r[i]==r[j]&&wv[i+1]<wv[j+1];
}

void sort(int *r,int *a,int *b,int n,int m)
{
     int i;
     for(i=0;i<n;i++)
wv[i]=r[a[i]];
     for(i=0;i<m;i++)
wk[i]=0;
     for(i=0;i<n;i++)
wk[r[a[i]]]++;
     for(i=1;i<m;i++)
wk[i]+=wk[i-1];
     for(i=n-1;i>=0;i--)
b[--wk[r[a[i]]]]=a[i];
     return;
}

void dc3(int* r,int* sa,int n,int m)
{
int *rn=r+n,*san=sa+n,ta=0,tbc=0,p=0;
int tb=(n+1)/3;
r[n]=r[n+1]=0;
for(int i=0;i<n;++i)
if(i%3!=0)
{
wa[tbc]=i;
++tbc;
}
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
p=1;
rn[F(wb[0],tb)]=0;
for(int i=1;i<tbc;++i)
{
if(!compare0(r,wb[i],wb[i-1]))
{
rn[F(wb[i],tb)]=p;
++p;
}
else
{
rn[F(wb[i],tb)]=p-1;
}
}
if(p<tbc)
{
dc3(rn,san,tbc,p);
}else
{
for(int i=0;i<tbc;++i)
san[rn[i]]=i;
}
for(int i=0;i<tbc;++i)
{
if(san[i]<tb)
{
wb[ta++]=san[i]*3;

}
}
    if(n%3==1)
    {
wb[ta]=n-1;
++ta;
}
sort(r,wb,wa,ta,m);
for(int i=0;i<tbc;++i)
{
wb[i]=G(san[i],tb);
wv[wb[i]]=i;
}
int i,j;
    for(i=0,j=0,p=0;i<ta&&j<tbc;++p)
    sa[p]=compare1(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(;i<ta;++p)
{
sa[p]=wa[i];
++i;
}
    for(;j<tbc;++p)
{
sa[p]=wb[j];
++j;
}
}

int min(int a,int b)
{
return a<b?a:b;
}

int st[MAX][17];
int mm[MAX];

void initRMQ(int *c,int* mm,int n)
{
int i=0,j=0,a=0,b=0;
mm[0]=-1;
for(i=1;i<=n;++i)
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
for(i=1;i<=n;++i)
st[i][0]=i;
for(i=1;i<=mm[n];++i)
for(j=1;j+(1<<i)<=n+1;++j)
{
a=st[j][i-1];
b=st[j+(1<<(i-1))][i-1];
if(c[a]<c[b])
st[j][i]=a;
else
st[j][i]=b;
}
return;
}

int askRMQ(int*mm,int* c,int a,int b)
{
if(a>b)
{
int t=a;
a=b;
b=t;
}
++a;
int t=mm[b-a+1];
b-=(1<<t)-1;
a=st[a][t];
b=st[b][t];
return c[a]<c[b]?a:b;
}

void hight(int* r,int* sa,int n)
{
for(int i=1;i<=n;++i)
rank[sa[i]]=i;
height[sa[0]]=0;
int k=0;
for(int i=0;i<n;++i)
{
int j=sa[rank[i]-1];
k=k?k-1:0;
for(;r[i+k]==r[j+k];++k)
;
height[rank[i]]=k;
}
}
/*.................................................*/

int main()
{
freopen("calfflac.in","r",stdin);
freopen("calfflac.out","w",stdout);
int t=0;
while(scanf("%c",&ab[t])!=EOF)++t;
for(int i=0;i<t;++i)
{
if('A'<=ab[i]&&ab[i]<='Z')
{
rb[n]=ab[i]-'A'+2;
point[n]=i;
++n;
}else if('a'<=ab[i]&&ab[i]<='z')
{
rb[n]=ab[i]-'a'+2;
point[n]=i;
++n;
}
}
rb[n]=1;
m=38;
int nn=n*2+1;
for(int i=n+1;i<nn;++i)
rb[i]=rb[2*n-i];
dc3(rb,sa,nn+1,m);
hight(rb,sa,nn);
initRMQ(height,mm,nn);

int now=0,max=0,now2=0,max2=0;
for(int i=0;i<n;++i)
{
if(rb[i]==rb[i+1])
{
int t=askRMQ(mm,height,rank[i+1],rank[2*n-i]);
if(height[t]>max2)
{
max2=height[t];
now2=i;
}
}
int t=askRMQ(mm,height,rank[i],rank[2*n-i]);
if(height[t]>max)
{
max=height[t];
now=i;
}
}
if(max*2-1>max2*2)
{
printf("%d ",max*2-1);
int a=point[now-max+1];
int b=point[now+max-1];
for(int i=a;i<=b;++i)
{
printf("%c",ab[i]);
}
printf(" ");
}else
{
printf("%d ",max2*2);
int a=point[now2-max2+1];
int b=point[now2+max2];
for(int i=a;i<=b;++i)
{
printf("%c",ab[i]);
}
printf(" ");
}
}