C++14(g++5.4) 解法, 执行用时: 27ms, 内存消耗: 12080K, 提交时间: 2019-11-28 23:13:51

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+8;
char ma[MAXN<<1],s[MAXN];
int p[MAXN<<1],cas=1;
int manacher(int len){
    int n=0,mx=0,id=0,ans=0;
    ma[n++]='$';
    ma[n++]='#';
    for(int i=0;i<len;++i){
        ma[n++]=s[i];
        ma[n++]='#';
    }ma[n]='@';
    for(int i=1;i<n;++i){
        p[i]=mx>i?min(mx-i,p[(id<<1)-i]):1;
        while(ma[i-p[i]]==ma[i+p[i]])p[i]++;
        if(mx<p[i]+i)id=i,mx=p[i]+i;
        ans=max(ans,p[i]);
    }return ans-1;
}
int main() {
    while(scanf("%s",s),s[0]^'E')
        printf("Case %d: %d\n",cas++,manacher(strlen(s)));
    return 0;
}

C++ 解法, 执行用时: 35ms, 内存消耗: 10128K, 提交时间: 2021-12-18 15:11:15

#include<bits/stdc++.h>
using namespace std;
char s[2000001];
int p[2000001],num;
int main(){
	while(cin>>s&&s[0]!='E'){
		int l=strlen(s),k=1,ml=0;
		for(int i=l;i>=0;i--)s[i+i+2]=s[i],s[i+i+1]='#';
		s[0]='*';
		for(int i=2;i<l+l+1;++i){
			int mr=k+p[k]-1;
			p[i]=min(p[2*k-i],max(mr-i+1,1));
			while(s[i-p[i]]==s[i+p[i]])++p[i];
			if(i+p[i]>k+p[k])k=i;
			if(p[i]>ml)ml=p[i];
		}
		cout<<"Case "<<++num<<": "<<ml-1<<"\n";
	}
	return 0;
}