自动搬运

查看原文

来自洛谷，原作者为

	L_zaa_L And in case i don't see you,good afternoon,good evening,and good night

搬运于2025-08-24 22:56:23，当前版本为作者最后更新于2024-03-25 14:16:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析

对于题目的限制，很容易想到如果是一个以这个位置为中点的回文串肯定是最好满足条件的，所以这个问题我们可以转换成找一个出现次数两次及以上的回文串的最大长度。

看到回文串，不难想到 manacher，我们可以对原串先跑一遍 manacher，然后现在我们需要判断有哪些回文串是相等的，我们发现长度有单调性，只要长的满足，短的也会满足，所以我们考虑二分长度，然后可以记录每个位置这个长度的 hash 值，然后再用 unordered map 就可以记录这个 hash 值是否出现过多次。

时间复杂度：$O(n\log n)$。

Code

#include<bits/stdc++.h>
#define int long long
#define N 2000005
using namespace std;
int n,p,mx,len[N];
int ans;
unsigned int f[N],Pow[N];//自然溢出
char a[N],b[N]; 
unordered_map<int,int> vis;
inline unsigned int g(int l,int r){
    return f[r]-f[l-1]*Pow[r-l+1];
}
inline bool check(int x){
    vis.clear();
    for(int i=1;i<=n;i++){
        if(x&1){
            if(len[i<<1]>=x){
                if(vis[g(i-(x>>1),i+(x>>1))]) return 1;
                vis[g(i-(x>>1),i+(x>>1))]=1;
            }
        }
        else{
            if(len[(i<<1)+1]){
                if(vis[g(i-(x>>1)+1,i+(x>>1))]) return 1;
                vis[g(i-(x>>1)+1,i+(x>>1))]=0;
            }
        }
    }
    return 0;
}
signed main(){
    scanf("%lld",&n);
	scanf("%s",a+1);
	for(int i=1;i<=n;i++){
		b[i<<1]=a[i];
		b[(i<<1)+1]='#';
	}
	b[0]='$';b[1]='#';b[n*2+2]='&';
	p=1,mx=1;
	for(int i=2;i<=2*n;i++){
		if(mx>=i) len[i]=min(len[2*p-i],mx-i);
		while(b[i+len[i]+1]==b[i-len[i]-1]) ++len[i];
		if(i+len[i]>mx) p=i,mx=i+len[i];
	}
	for(int i=1;i<=n;i++) f[i]=f[i-1]*131+(a[i]-'a');
    Pow[0]=1;
    for(int i=1;i<=n;i++) Pow[i]=Pow[i-1]*131;
    int l=0,r=n/2+1;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid*2)) ans=mid*2,l=mid+1;
        else r=mid-1;
    }
    l=0,r=n/2+1;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid*2+1)) ans=max(ans,mid*2+1),l=mid+1;
        else r=mid-1;
    }
    printf("%lld",(ans+1)/2);
	return 0;
}