记录编号 |
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;
}