提交时间:2025-01-21 08:00:27

运行 ID: 349783

#include<bits/stdc++.h> using namespace std; char ss[100010],s[200010]; int len,l[200010],mid=1,r=1; int le[200010],ri[200010];//从左边右边来的在这个点结束的最长回文串的半径 int maxx,t; int main() { scanf("%s",ss); len=strlen(ss); s[0]='*'; len=2*len+1; for(int i=1;i<=len;i++) { if(i%2==1) s[i]='#'; else s[i]=ss[i/2-1]; } l[1]=1; for(int i=2;i<=len;i++) { if(i<r) l[i]=min(l[2*mid-i],r-i); else l[i]=1; while(s[i+l[i]]==s[i-l[i]]) l[i]++; if(i+l[i]>r) mid=i,r=l[i]+i; if(i+l[i]-1<=len) le[i+l[i]-1]=max(le[i+l[i]-1],l[i]); if(i-l[i]+1>=1) ri[i-l[i]+1]=max(ri[i-l[i]+1],l[i]); } for(int i=1;i<=len;i++) ri[i]=max(ri[i],ri[i-1]-1); for(int i=len;i>=1;i--) le[i]=max(le[i],le[i+1]-1); for(int i=1;i<=len;i+=2) { if(le[i]+ri[i]>maxx) { maxx=le[i]+ri[i]; t=i; } } printf("%d",maxx-2); return 0; }