文档介绍：// 最长回文子串模板
//hdu3068 ,最长回文子串模板, Manacher算法,时间复杂度
O(n) ,相当快
#include <iostream>
#include <cstdio>
#include <cstring>
using namespacestd;
#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 namespacestd;
#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