#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=110010;
char str[N];
char cpy[N*2];
int rad[N*2];
void init()
{
cpy[0]='@';
int n=strlen(str);
for(int i=0;i<n;i++)
{
cpy[i*2+1]='#';
cpy[i*2+2]=str[i];
}
cpy[n*2+1]='#';
cpy[n*2+2]='\0';
}
void manacher()
{
int id=0,ma=0;//id:当前回文串中心 ma:当前回文串右边界
int len=strlen(cpy);
for(int i=1;i<len;i++)//i:正在处理的右部点
{
if(ma>i)
{
rad[i]=ma-i<rad[2*id-i]?ma-i:rad[2*id-i];//2*id-i：左部点
}
else
{
rad[i]=1;//回文半径设为1，暴力扩张
}
while(cpy[i+rad[i]]==cpy[i-rad[i]]) rad[i]++;
if(i+rad[i]>ma)//更新右边界
{
id=i;
ma=id+rad[i];
}
}
int mx=0;
for(int i=1;i<len;i++)
{
if(rad[i]>mx) mx=rad[i];
}
printf("%d\n",mx-1);
}
int main()
{
int j=0;
while(~scanf("%s",str))
{
init();
manacher();
}
}
Manacher_最长回文子串
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- ------------6.11更新-----------明天（tuo yan）继续把 Basic & Tall刷...
