大家好，我们又见面了！！！今天是2025年9月3日。上一期，我给大家介绍了 Manacher 算法，今天我将带领大家使用 Manacher 算法解决几道相关的算法题目。
开始之前还是希望没有学过 Manacher 的话，先看一下我的上一篇文章：Manacher 算法。
废话不多说，我们开启今天的内容~~~
题目一：ABB
【题目描述】
【算法原理】
因为我们只被允许从末尾添加字符，所以：
我们只需要找到给定字符串的最长回文后缀的长度，再用字符串总长度减去最长回文后缀的长度就可以了。
我们之前使用 KMP 算法解决过这道问题，想要了解的可以去看一下：四道 KMP 相关算法题
但是，我们学完 Manacher 算法之后，遇到回文串的问题，首先考虑 Manacher 算法能不能解决，这道题目可以使用 Manacher 算法解决，将字符串预处理之后，使用 Manacher 算法求出回文半径数组，每求完一个位置，都去看一看该位置的回文串是否是回文后缀，是的话就更新结果。
【代码实现】
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int m, n;
string t, s;
int d[N];
int main()
{
cin >> m >> t;
s += ' ';
for(auto ch : t)
{
s += '#'; s += ch;
}
s += "##";
n = s.size() - 2;
int ret = 1;
d[1] = 1;
for(int i = 2, l = 1, r = 1; i <= n; i++)
{
int len = r >= i ? min(d[r - i + l], r - i + 1) : 1;
while(s[i + len] == s[i - len]) len++;
if(i + len - 1 > r) r = i + len - 1, l = i - len + 1;
d[i] = len;
if(i + d[i] - 1 == n) ret = max(ret, d[i] - 1);
}
cout << m - ret << endl;
return 0;
}题目二：啦啦队排练
【题目描述】
【题目解析】
拿到这类题目描述很长的题目之后，首先来模拟一下输入输出样例。看能否得出一些思路：
其实这道题就是在一个字符串中，找出所有长度为奇数的回文串，将其中前k大的累乘起来。
【算法原理】
Manacher 算法就可以解决找出所有长度为奇数的回文串：只需要最终枚举真正的字符而不是 '#'，就可以了。
‘#’ 的话实质上是原字符串两个字符之前的空隙，枚举 ‘#’ 的话找的是偶回文串。
因此，首先使用 Manacher 算法将回文半径数组预处理出来。
其次，我们发现，如果一个子串的长度 d[i] - 1为奇数的话，那么根据之前讲过的回文串删去首尾字符还是回文串的性质一定还会有长度为 d[i] - 3，d[i] - 5，d[i] - 7……长度的奇回文串。
思考：如何找出前 K 大？？？
方法一：收集 + 排序（不可行）
长度为奇数的回文串数量太多了，如果想要将长度都收集下来然后排序，时间和空间都是不够的。
方法二：词频统计 + 前缀和（正解）
cnt[i] ：表示：奇数长度最长为 i 时，一共出现了多少次。
【代码实现】
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e6 + 10, mod = 19930726;
LL m, n, k;
string t, s;
LL d[N], cnt[N];
LL qpow(LL a, LL b, LL p)
{
LL ret = 1;
while(b)
{
if(b & 1) ret = ret * a % p;
a = a * a % p;
b >>= 1;
}
return ret;
}
int main()
{
cin >> m >> k >> t;
s += ' ';
for(auto ch : t)
{
s += '#';
s += ch;
}
s += "##";
n = s.size() - 2;
// manacher 㷨
d[1] = 1;
for(int i = 2, l = 1, r = 1; i <= n; i++)
{
int len = r >= i ? min(d[r - i + l], r - i + 1ll) : 1;
while(s[i + len] == s[i - len]) len++;
if(i + len - 1 > r) r = i + len - 1, l = i - len + 1;
d[i] = len;
}
// ͳƴƵ
for(int i = 2; i <= n; i += 2) cnt[d[i] - 1]++;
// ͳƽ
LL ret = 1, sum = 0;
for(int i = m / 2 * 2 + 1; i >= 1; i -= 2)
{
sum += cnt[i];
ret = ret * qpow(i, min(sum, k), mod) % mod;
k -= sum;
if(k <= 0) break;
}
if(k > 0) cout << -1 << endl;
else cout << ret << endl;
return 0;
} 题目三：ANT-Antisymmetry
题目链接：P3501 [POI 2010] ANT-Antisymmetry - 洛谷
【题目描述】
【题目解析】
我们依然先去分析输入输出样例：
不难得出反对称字符串的特点：
1. 反对称字符串长度一定是偶数，长度为奇数的字符串一定不会是反对称字符串。
2. 反对称字符串中心两侧的字符，是相反的字符。
【算法原理】
根据上面得出的反对称字符串的特点，我们仍然可以使用 Manacher 算法，但是需要做出一些更改：
注意：如果最右回文串是以 0 / 1 为中心的话，那么就会推导错误：
如果最右回文串是以 # 为中心，不会推导错误：
因此，我们在填写回文半径数组时，只枚举 ‘#’（否则会发生错误）。
【代码实现】
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int m, n;
string t, s;
int d[N];
bool check(int i, int j)
{
if(s[i] == '0' && s[j] == '1') return true;
else if(s[i] == '1' && s[j] == '0') return true;
else if(s[i] == '#' && s[j] == '#') return true;
return false;
}
int main()
{
cin >> m >> t;
s += ' ';
for(auto ch : t)
{
s += '#';
s += ch;
}
s += "##";
n = s.size() - 2;
d[1] = 1;
LL ret = 0;
for(int i = 3, l = 1, r = 1; i <= n; i += 2)
{
int len = r >= i ? min(d[r - i + l], r - i + 1) : 1;
while(check(i + len, i - len)) len++;
if(i + len - 1 > r) r = i + len - 1, l = i - len + 1;
d[i] = len;
ret = ret + d[i] / 2;
}
cout << ret << endl;
return 0;
}题目四：最长双回文串
【题目描述】
【算法原理】
解法：枚举 + Manacher 算法
step1. 枚举所有的分割点‘#’：
step2. 预处理 L，R 两个数组：
利用 manacher 算法生成的回文半径数组，预处理 L，R 两个数组。
【代码实现】
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int m, n;
string t, s;
int d[N], l[N], r[N];
int main()
{
cin >> t; m = t.size();
s += ' ';
for(auto ch : t)
{
s += '#'; s += ch;
}
s += "##";
n = s.size() - 2;
d[1] = 1;
for(int i = 2, l = 1, r = 1; i <= n; i++)
{
int len = r >= i ? min(d[r - i + l], r - i + 1) : 1;
while(s[i + len] == s[i - len]) len++;
if(i + len - 1 > r) r = i + len - 1, l = i - len + 1;
d[i] = len;
}
// Ԥ l,r
for(int i = 1, j = 1; i <= n; i++)
{
while(j < i + d[i])
{
l[j] = j - i;
j += 2;
}
}
for(int i = n, j = n; i >= 1; i--)
{
while(j > i - d[i])
{
r[j] = i - j;
j -= 2;
}
}
// ½
int ret = 0;
for(int i = 3; i <= n - 2; i += 2)
ret = max(ret, l[i] + r[i]);
cout << ret << endl;
return 0;
}好的，今天的分享就到这里了，谢谢大家，期待下一次相遇！！！