最长回文子串长度
作者:
无苦邪
,
2024-04-16 17:38:07
,
所有人可见
,
阅读 3
//#include<bits/stdc++.h>
//using namespace std;
//// char str[50];
//string str;
//int main() {
// int i,j,n,m,k,t,l;
// // gets(str);
// getline(cin,str);
// l=str.size();
// // i表示子串的长度
// for(i=l; i>=2; i--) {
// // 而这里的j则用作子串的起始索引
// for(j=0; j+i<l; j++) {
// for(k=j,t=j+i; k<=t; k++,t--) {
// if(str[k]!=str[t])
// break;
// }
// if(k>t)
// break;
// }
//
// // 说明已经遇到最长的了
// // 因为子串长度是从最长的开始
// if(j+i<l)
// break;
// }
// cout << i << j;
// if(i>=2)
// printf("%d",i+1);
// else
// printf("1");
// return 0;
//}
//
//
////Is PAT&TAP symmetric?
/*
manacher算法
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
string s;
// 定义数组p[i] 以i为中点的回文子串的半径
int p[2010];
int main() {
getline(cin,s);
// id表示已知最大长度回文子串的中心位置
int len=s.length(),id=0,maxlen=0;
// 将数组用符号填充,每两个字符之间插入一个#
// 使得字符串转变为奇数
// #s[i]#
for(int i=len; i>=0; --i) {
s[i+i+2]=s[i];
s[i+i+1]='#';
}
s[0]='*';
// id作为半径范围l
for(int i=2; i<2*len+1; ++i) {
// 如果已知最大回文长度包含了当前i
if(p[id]+id>i)
//p[2 * id - i] i 关于 id 的对称位置的回文半径的。
p[i] = min(p[2 * id - i] ,p[id] + id - i);
// p[i]=p[2*id-i]<p[id]+id-i?p[2*id-i]:p[id]+id-i;
// 如果不包含,则重新开
else
p[i]=1;
// 若左右点相等,则继续拓展
while(s[i-p[i]] == s[i+p[i]])
++p[i];
// 更新最大回文长度中点和半径
if(id+p[id]<i+p[i])
id=i;
if(maxlen<p[i])
maxlen=p[i];
}
printf("%d\n",maxlen-1);
return 0;
}