#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=1000010;
char tmp[M<<1],s[M];
int Len[M<<1];

int Init(char *s){
	int len=strlen(s);
	tmp[0]='@'; //特殊字符作为前越界判断
	for(int i=1;i<=len<<1;i+=2){
		tmp[i]='#'; // 插入特殊字符作为标记 
		tmp[i+1]=s[i>>1];
	} 
	tmp[len*2+1]='#';
	tmp[len*2+2]='$';
	tmp[len*2+3]=0;
	return len*2+1;
}

int Manacher(char *st,int len){
	int mx=0,ans=0,po=0; //mx为最大值
	for(int i=1;i<=len;i++){
		if(mx>i)
			Len[i]=min(mx-i,Len[po*2-i]);
		else 
			Len[i]=1;
		while(st[i-Len[i]]==st[i+Len[i]])
			Len[i]++;
		if(Len[i]+i>mx){
			mx=Len[i]+i;
			po=i;
		}
		ans=max(ans,Len[i]);
	} 
	return ans-1;
}

int main(){
	int ln;
	cin>>s;
	ln=Init(s);
	cout<<Manacher(tmp,ln)<<"\n";
	return 0;
}

 

0 0 votes
文章评分

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments