HiHo 1032 最长回文子串 (Manacher算法求解)

/**
* 求解最长回文字串,Manacher算法o(n)求解最长回文子串问题
**/ #include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#define L 2000050
using namespace std;
char line[L],str[L];
int cnt[L],len1,len2; int main(){
int ans,t,i,j;
scanf("%d",&t);
while(t--){
scanf("%s",line);
len1=strlen(line);
len2=;
str[len2++]='$';
str[len2++]='#';
for(i=;i<len1;i++){
str[len2++]=line[i];
str[len2++]='#';
}
str[len2]='\0';
memset(cnt,,sizeof cnt);
for(i=,j=;i<len2;i++){
if(cnt[j]+j>i)cnt[i]=min(cnt[*j-i],cnt[j]-(i-j));
else cnt[i]=;
for(;str[i-cnt[i]] == str[i+cnt[i]];cnt[i]++);
if(i+cnt[i]>j+cnt[j])j=i;
}
//puts(str);
ans=;
for(i=;i<len2;i++)
{
// printf("%d ",cnt[i]);
if(ans<cnt[i])ans=cnt[i];
}
printf("%d\n",ans-);
}
return ;
}
上一篇:hihocoder #1032 : 最长回文子串 Manacher算法


下一篇:hihocoder 1032 最长回文子串(Manacher)