前置知识

题意简化

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

解题过程

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

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

这个时候就要用到 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}

，但是该怎么判断呢？

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

代码

CPP

#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;
}

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

文章操作