记录编号	578473	评测结果	AAAA
题目名称	[POJ 3974]最长回文子串	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2023-03-18 09:18:47	内存使用	29.13 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

char s[11000002];
char s_new[21000002];//存添加字符后的字符串 
int p[21000002];

int Init() {//形成新的字符串 
    int len=strlen(s);//len是输入字符串的长度
    s_new[0]='$';//处理边界，防止越界 
    s_new[1]='#';
    int j=2; 
    for(int i=0;i<len;i++) {
        s_new[j++]=s[i];
        s_new[j++]='#';
    } 
    s_new[j]='\0';//处理边界，防止越界（容易忘记） 
    return j;// 返回s_new的长度 
}

int Manacher() {//返回最长回文串 
    int len=Init();//取得新字符串的长度， 完成向s_new的转换
    int max_len=-1;//最长回文长度
    int id;
    int mx=0;
    for(int i=1;i<=len;i++) {
        if(i<mx)
            p[i]=min(p[2*id-i],mx-i);//上面图片就是这里的讲解 
        else p[i]=1;
        while(s_new[i-p[i]]==s_new[i+p[i]])//不需边界判断，因为左有'$'，右有'\0'标记；
            p[i]++;//mx对此回文中点的贡献已经结束，现在是正常寻找扩大半径
        if(mx<i+p[i]) {//每走移动一个回文中点，都要和mx比较，使mx是最大，提高p[i]=min(p[2*id-i],mx-i)效率 
            id=i;//更新id 
            mx=i+p[i];//更新mx 
        }
        max_len=max(max_len,p[i]-1); 
    } 
    return max_len; 
}
 
int main(){
	freopen("palindrome.in","r",stdin);
	freopen("palindrome.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>s;
    int i=1;
    while(s[0]!='E'&&s[1]!='E'&&s[2]!='E'){
    	cout<<"Case "<<i<<": "<<Manacher()<<endl;
    	cin>>s;
    	i++;
	}
    return 0;
}