文档介绍：//最长回文子串模板
//hdu3068,最长回文子串模板,Manacher算法,时间复杂度O(n),相当快
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define M 20000050
char str1[M],str[2*M];//start from index 1
int rad[M],nn,n;
void Manacher(int *rad,char *str,int n)/*str是这样一个字符串(下标从1开始):
举例:若原字符串为"abcd",则str为"$#a#b#c#d#",最后还有一个终止符。
n为str的长度,若原字符串长度为nn,则n=2*nn+2。
rad[i]表示回文的半径,即最大的j满足str[i-j+1...i] = str[i+1...i+j],
而rad[i]-1即为以str[i]为中心的回文子串在原串中的长度*/
{
int i;
int mx = 0;
int id;
for(i=1; i<n; i++)
{
if( mx > i )
rad[i] = rad[2*id-i]<mx-i?rad[2*id-i]:mx-i;
else
rad[i] = 1;
for(; str[i+rad[i]] == str[i-rad[i]]; rad[i]++)
;
if( rad[i] + i > mx )
{
mx = rad[i] + i;
id = i;
}
}
}
int main()
{
int i,ans,Case=1;
while(scanf("%s",str1)!=EOF)
{
nn=strlen(str1);
n=2*nn+2;
str[0]='$';
for(i=0;i<=nn;i++)
{
str[2*i+1]='#';
str[2*i+2]=str1[i];
}
Manacher(rad,str,n);
ans=1;
for(i=0;i<n;i++)
ans=rad[i]>ans?rad[i]:ans;
printf("%d\n",ans-1);
}
return 0;
}
//扩展kmp版,时间复杂度O(nlogn),稍慢
//hdu3068
/*给一个w长的字符串,求最长回文子串的长度
解题思路:不是传说中的高深的后缀数组,而是扩展的kmp算法。
扩展kmp中,模式串与主串都有一个next向量,相应的next[i],记录该串的后缀与模式串的最大匹配数,关于扩展kmp的具体实现这里就不说了,现在只说一下解此题的思路:
令所给字符串为a,则找到中点mid位置,一后半段做为模式串,把a倒过来生成b,求出b串在该模式串的每一位的next1[i];在以字符串a的前半段的逆串作为模式串,求出a串在该模式串下的next2。然后遍历a串的每一位,根据next1和next2就可以判断此处是否回文,但这个回文只能判断跨越中点mid的回文,因
此这里要进行划分递归,分别在a的前半段和后半段重复此算法即可找到最大回文串。
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 110005
char tmp1[N],tmp2[N],s[N],tt[N];
int tmp[N],ans,ne1[N],ne2[N];
char *rev(char *str,int ll)
{
for(int i=0;i<ll;i++)
tt[i]=str[ll-i-1];
tt[ll]=0;
return tt;
}
void getA(char *pat,int *aa)
{
int j=0;
while(pat[1+j] && pat[j]==pat[1+j])
j++;
aa[1]=j;
int k=1;
int len,l;
for(int i=2;pat[i];i++)
{
len=k+aa[k];
l=aa[i-k];
if(l<len-i)
aa[i]=l;
else
{
j=(0>len-i)?0:len-i;
while(pat[i+j] && pat[j]==pat[i+j])
j++;
aa[i]=j;
k=i;
}
}
}
void getB(cha