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

· · 题解

前置知识

KMP，模板题传送门。

题意简化

给一个字符串，现在允许将字符串中一个任意长度的子串删除，问删除后的字符串的最长回文前后缀是多少？

解题过程

删除字符串的一段，只有三种情况：删开头、删中间、删结尾。问题是我们应该删去哪一部分呢？

显然应该保留原字符串中已经有的回文前后缀，然后就单独看剩下的中间字符串，这时的字符串已经没有回文前后缀了，所以只能删开头或结尾才能最优。现在的问题是要怎么删除开头或结尾？

这个时候就要用到 KMP 了，如果剩下有一个字符串 S = \texttt{cdebijb}，要删除一段前缀或后缀使得剩下的一段有回文前后缀。因为回文前后缀两段是相反的，而 KMP 中求的前后缀是要完全相同的，针对这个情况，我们可以做的就是把字符串 S 复制一遍，再倒置放在原串旁边（要注意需要用一个不与字符串中任意一个字符相同的字符连接）。例如字符串 S 可以给它变成 \texttt{cdebijb*bjibedc} 和 \texttt{bjibedc*cdebijb}，这两个串分别可以用来找字符串 S 的前缀的回文前后缀和 S 的后缀的回文前后缀（有点绕，请细读）。对两个字符串分别求最长公共前后缀，取 next 数组的最大值，结果再加上原字符串的最长回文前后缀就是答案了。

一个问题

你以为这样就结束了吗？错，大错特错！
前面写的大家可能看不懂，我们用字符串 S = \texttt{abcaaaaba} 来模拟一遍。

首先找到原有字符串的回文前后缀，发现是 \texttt{ab} 和 \texttt{ba}，去掉后字符串为 \texttt{caaaa}。按照上述方法复制一遍再倒置放旁边，这两个串为 \texttt{caaaa*aaaac} 和 \texttt{aaaac*caaaa}，如果直接取 next 数组最大值，会发现结果是 4，也就是 \texttt{aaaa}。但是这里的前缀和后缀不能重叠，所以只能是 \texttt{aa}，但是该怎么判断呢？

如果这一串是回文前后缀之一，那么肯定还有另一段回文前后缀，如果把它加上总长度还是小于或等于整个字符串的长度时，就说明这一段回文前后缀是合法的，反之不合法。到此就解决了所有问题，快去写代码吧！

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int dg, nxt[N << 2];
void init_nxt(string s){//计算nxt数组 
    int j = 0, len = s.size();
    for(int i = 1;i < len;i++){
        while(j && s[i] != s[j]) j = nxt[j - 1];
        if(s[i] == s[j]) j++;
        nxt[i] = j;
    }
}
int solve(string str){
    string str2 = str, str3, str4;
    reverse(str2.begin(), str2.end());//字符串反转的好用函数 
    str3 = str2 + '*' + str, str4 = str + '*' + str2;//拼接字符串 
    init_nxt(str3);//计算nxt数组 
    int maxn = -1, zlen = str3.size();
    for(int i = str2.size() + 1;i < zlen;i++){
        if(nxt[i] > maxn && i + nxt[i] < zlen) maxn = nxt[i];
        //为什么题解里是小于或等与总长度而这里是小于总长度呢？因为这里的i表示的是下标而非长度（字符串下标从0开始） 
    }
    memset(nxt, 0, sizeof(nxt));
    init_nxt(str4);
    //同样的做法 
    for(int i = str2.size() + 1;i < zlen;i++){
        if(nxt[i] > maxn && i + nxt[i] < zlen) maxn = nxt[i];
    }
    return maxn;
}
string str;
int main(){
    cin >> str;
    int len = str.size(), z1 = 0, z2 = len - 1;
    //先求原字符串的回文前后缀 
    while(str[z1] == str[z2] && z1 <= z2){
        z1++, z2--;
    }
    str = str.substr(z1, str.size() - z1 * 2);//去掉回文前后缀的字符串（substr很好用） 
    int hw = solve(str);
    if(hw == -1) hw = 0;
    cout << hw + z1;//计算答案 
    return 0;
}