题目链接:https://www.luogu.com.cn/problem/P3805#submit
题意:给定长为n的字符串,求最大回文子串的长度。(n<=1.1e7)
思路:
manacher板子,时间复杂度O(n)。
AC code:
/* * manacher板子--求最大回文串的长度 * O(n) */ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=11000005; int n,ans,p[maxn<<1]; char ss[maxn],s[maxn<<1]; void init(){ s[0]='~',s[1]='|'; for(int i=0;i<n;++i) s[2*i+2]=ss[i],s[2*i+3]='|'; n=2*n+2; } void manacher(){ int mid=0,r=0; for(int i=1;i<n;++i){ if(i<=r) p[i]=min(p[(mid<<1)-i],r-i+1); while(s[i-p[i]]==s[i+p[i]]) ++p[i]; //暴力扩展,r递增,所以算法是线性的 if(i+p[i]>r) r=i+p[i]-1,mid=i; ans=max(ans,p[i]); } } int main(){ scanf("%s",ss); n=strlen(ss); init(); manacher(); printf("%d ",ans-1); return 0; }