Description
据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观(最棒的回文)。
在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母'A'-'Z'和'a'-'z'。要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。我们将保证最长的回文不会超过2,000个字符(在除去标点符号、空格之前)。
Input
输入不会超过20,000字符。这个文件可能一行或多行，但是每行都不超过80个字符(不包括最后的换行符)。
Output
输出的第一行应该包括找到的最长的回文的长度。
下一行或几行应该包括这个回文的原文（没有除去标点符号、空格），把这个回文输出到一行或多行（如果回文中包括换行符）。
如果有多个回文长度都等于最大值，输出最前面出现的那一个。
Sample Input
Confucius say: Madam, I'm Adam.
Sample Output
11
Madam, I'm Adam
题解
后缀数组模板中的(Lcp)可以求出(Height[])，由此可以知道两个相邻名次的最长公共前缀，好像这题和这个有点沾边……
我们可以把原串化为大小写统一的的字母串，然后在末尾加一个奇特字符或赋一个特殊值，最后将它反转赋值到末尾，按照后缀模板加另一个特殊值
求出经过上述处理后的串的(height[])，在求出最长前缀即可
(PS:)关于(id)数组的技巧请读者另行思考
(My~code)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=50000;
int n,ln,id[N],sa[N],rk[N],tmp[N],c[N],height[N];
string ss;
char s[N];
void Read()//读入加反转
{
string str;
for(getline(cin,ss);getline(cin,str);ss+='
'+str);
int len=ss.length();
n=0;
for(int i=0;i<len;++i)
{
if(ss[i]>='a'&&ss[i]<='z')
s[n]=ss[i],id[n]=i,++n;
if(ss[i]>='A'&&ss[i]<='Z')//字符要统一大小写
s[n]=ss[i]+'a'-'A',id[n]=i,++n;
}
for(int i=0;i<n;++i) s[n+n-i]=s[i];
s[n]=2,s[n+n+1]=1;
ln=n,n=n+n+2;
}
void Make_Sa()//后缀数组的模板——求sa[]与rank[]
{
int i,j,len,na;
na=256;
memset(c,0,na*sizeof(int));
for(i=0;i<n;++i)
{
rk[i]=s[i]&0xff,
++c[rk[i]];
}
for(i=1;i<na;++i) c[i]+=c[i-1];
for(i=0;i<n;++i)
{
--c[rk[i]],
sa[c[rk[i]]]=i;
}
for(len=1;len<n;len<<=1)
{
for(i=0;i<n;++i)
{
j=sa[i]-len;
if(j<0) j+=n;
tmp[c[rk[j]]++]=j;
}
c[0]=0,j=0,
sa[tmp[0]]=0;
for(i=1;i<n;++i)
{
if(rk[tmp[i]]!=rk[tmp[i-1]]
||rk[tmp[i]+len]!=rk[tmp[i-1]+len])
c[++j]=i;
sa[tmp[i]]=j;
}
memcpy(rk,sa,n*sizeof(int)),
memcpy(sa,tmp,n*sizeof(int));
if(j>=n-1) break;
}
}
void Lcp()//后缀数组的模板——求Height[]
{
int i=0,j,k=0;
height[0]=0;
for(j=rk[0];i<n-1;++i,++k)
for(;k>=0&&s[i]!=s[sa[j-1]+k];)
{
height[j]=k, --k;
j=rk[sa[j]+1];
}
}
void PutAns()
{
int ID=0,Ans=0;
for(int i=1;i<n;++i)
{
if(sa[i]<ln&&sa[i-1]>ln)//必须一个为原字母串，另一个为反转字母串
if((height[i]>Ans)
||(height[i]==Ans&&sa[i]<ID))//坑点：还有字母最靠前
Ans=height[i],ID=sa[i];
if(sa[i]>ln&&sa[i-1]<ln)
if(height[i]>Ans
||(height[i]==Ans&&sa[i-1]<ID))
Ans=height[i],ID=sa[i-1];
}
printf("%d
",Ans);
for(int i=id[ID];i<=id[ID+Ans-1];++i)//id的巧处
printf("%c",ss[i]);
}
int main()
{
Read(),Make_Sa(),Lcp(),PutAns();
return 0;
}