题解：P10915 [蓝桥杯 2024 国 B] 最长回文前后缀

· · 题解

字符串哈希 + 二分 + 贪心

第一步贪心：考虑到可以删去某一段子串，且对于一段长度 k，若满足 s_{1 \sim k} = s_{n-k+1 \sim n}，即初始时前后缀已经存在一个长度为 k 的回文前后缀，那么这一段保留一定不会更劣。这个过程可以用双指针维护。注意特判当不存在满足 k \in [1,n],s_k \ne s_{n-k+1} 的 k 时直接输出 \left \lfloor \dfrac{n}{2} \right \rfloor，因为要避免相交。

那么问题就转化为在 s_{k+1 \sim n-k} 这一段中删去某个子串，使得这部分删除某个子串后的前后缀更大，然后将这个答案与一开始的 k 加起来即总长度。

第二步贪心：令 s^\prime =s_{k+1 \sim n-k}，且记 |s^\prime| 为 cnt，那么对于 s^\prime 这部分怎么删除子串更优呢？考虑贪心策略，不难发现因为 s^\prime_{1} \ne s^\prime_{cnt}，因此删除中间某部分肯定不优，因为首尾已经不匹配，中间删了等于白删。所以显然最优的策略应该是删除一段前缀或后缀。

那么可以分类讨论，先讨论删除前缀的情况，再讨论删除后缀的情况，最后取最大值。

以删除前缀时为例，删除后缀同理：

考虑枚举删除前缀的长度 i，则我们需要求 s^\prime _{i+1 \sim cnt} 这段中的最长公共前后缀长度，如何快速求解最长公共前后缀长度？经典套路了，考虑字符串哈希 + 二分快速求解即可。对最长公共前后缀长度进行二分答案，单调性显然是满足的。

假设当前二分的长度为 len，为了避免当前判定的前缀串与后缀串出现相交的情况，即要满足 i+1+(len-1) \lt cnt-(len-1)，移项得 2 \times len \lt cnt-i+1，即 2 \times len \le cnt-i，即 len \le \left \lfloor \dfrac{cnt-i}{2} \right \rfloor，因此二分长度的左右边界为 l=0,r=\left \lfloor \dfrac{cnt-i}{2} \right \rfloor。

代码如下：

#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef unsigned long long ULL;
const int N=5e5+5,P=13331;
int n;
char tmp[N],s[N],t[N];
ULL hs[N],ht[N],p[N];
void calc(ULL h[],char *s){
    p[0]=1;
    int len=strlen(s+1);
    rep(i,1,len){
        h[i]=h[i-1]*P+s[i];
        p[i]=p[i-1]*P;
    }
}
ULL getstr(ULL h[],int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
void solve(){
    scanf("%s",tmp+1);
    int n=strlen(tmp+1);
    int L=1,R=n;
    while(tmp[L]==tmp[R] && L<=R) L++,R--;
    if(L>R) return cout<<n/2,void();
    int cnt=0;
    rep(i,L,R) s[++cnt]=tmp[i];
    rep(i,1,cnt) t[i]=s[i];
    reverse(t+1,t+1+cnt);
    calc(hs,s);
    calc(ht,t);
    int ans=0;
    rep(i,1,cnt-1){ // 删除前缀
        int l=0,r=(cnt-i)/2;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(getstr(hs,i+1,i+mid)==getstr(ht,1,mid)) l=mid;
            else r=mid-1;
        }
        ans=max(ans,l);
    }
    rep(i,1,cnt-1){ // 删除后缀
        int l=0,r=(cnt-i)/2;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(getstr(ht,i+1,i+mid)==getstr(hs,1,mid)) l=mid;
            else r=mid-1;
        }
        ans=max(ans,l);
    }
    cout<<ans+(L-1);
}