自动搬运

查看原文

来自洛谷，原作者为

	cosmicAC 应无所住 而生其心

搬运于2025-08-24 21:58:34，当前版本为作者最后更新于2018-06-30 19:05:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

楼下 or 楼上的dalao对不起，现在我成为最快且最短的一份代码了。

这道题显然不是什么<=6特判的乱搞，其实也不应该是O(n * a(n))的并查集，正确的做法是线性的：考虑所有O(n)个本质不同的回文串，对每个回文串都可以O(1)判断。具体实现中,只需要在manacher中mx更新时,判断所有新出现的回文串的前一半是否为回文串即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
char s[1000010]={'?'};
int p[1000010],n,ans;
void manacher(char *s,int n){
    for(int c=0,mx=0,i=1;i<=n;i++){
        p[i]=i<mx?min(p[2*c-i],mx-i):1;
        while(s[i+p[i]]==s[i-p[i]])++p[i];
        if(i+p[i]>mx){
        	if(i&1)for(int j=max(mx,i+4);j<i+p[i];j++)
				if(!(j-i&3) && p[i-(j-i)/2]>(j-i)/2)ans=max(ans,j-i);
			mx=i+p[i],c=i;
		}
    }
}
int main(){
	scanf("%d %s",&n,s+1);
    for(int i=n;i;i--)s[i*2+1]='#',s[i*2]=s[i];s[1]='#';
    manacher(s,2*n+1);
    printf("%d\n",ans);
    return 0;
}