计算出字符串中以每个字符为对称中心的最长回文串的长度加\(1\)的值。
时间复杂度为\(O(n)\)。
#include<bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PLI pair<LL,int>
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=1e7+2e6;
int p[3*maxn],len1,len2;
char s[maxn],str[3*maxn];
void init(){
len1=strlen(s);
len2=2*len1+2;
str[0]='$';
str[1]='#';
for(int i=0;i<len1;i++){
str[i*2+2]=s[i];
str[i*2+3]='#';
}
}
void manacher(){
int id,mx=0;
for(int i=1;i<len2;i++){
if(mx>i) p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
for(;str[i-p[i]]==str[i+p[i]];p[i]++);
if(i+p[i]>mx){
mx=i+p[i];
id=i;
}
}
}
int main(){
scanf("%s",s);
init();
manacher();
int ans=0;
for(int i=1;i<len2;i++){
ans=max(ans,p[i]);
}
printf("%d\n",ans-1);
}
模板题:hdu3068 最长回文
原文链接: https://www.cnblogs.com/fxq1304/p/13227852.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/361487
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!