题解：P10271 漫长悄悄话

_zaa_ · 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;
}