题解：具体实现时，就是在更新mr时维护前半段是回文串的最长回文串就好了
正确性的话，因为到i时如果i+RL[i]-1<=mr，那么答案肯定在i之前就维护过了；
因此只有在i+RL[i]-1>mr时需要维护答案
由于mr最多被更新N<<1次，所以时间效率是对的；在找前半段最长的回文串时，记得从外向内枚举，一旦发现答案就立即break，否则效率会假
最后，注意只需要判前半段是否满足条件就好了，一是因为我们不清楚后半段相应位置的真实RL值，二是这是个回文串，左右是相等的。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn=(5e5)+;
int N,len,mid,mr,RL[maxn<<],ans=,a;
char O[maxn],S[maxn<<];
inline void Manacher(){
mid=mr=;
for(int i=;i<=len;i++){
if(i<mr)RL[i]=min(mr-i,RL[(mid<<)-i]);
else RL[i]=;
while(S[i-RL[i]]==S[i+RL[i]])RL[i]++;
if(i+RL[i]->mr){
mr=i+RL[i]-;
mid=i;
if(S[i]=='#'){
for(int j=RL[i]-;j>=;j-=){
a=i-(j>>);
if(a>=&&S[a]=='#'&&a+RL[a]->=i){
ans=max(ans,j);
break;
}
}
}
}
}
return;
}
int main(){
scanf("%d",&N);
scanf("%s",O);
S[]='$';
S[len=]='#';
for(int i=;i<N;i++){
S[++len]=O[i];
S[++len]='#';
}
Manacher();
printf("%d\n",ans);
return ;
}
By:AlenaNuna