自动搬运

查看原文

来自洛谷，原作者为

	littlesnake 渣渣老师骑着三轮车

搬运于2025-08-24 22:55:22，当前版本为作者最后更新于2024-02-17 19:27:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

看别人枚举字串状态，我表示无语，赛时还以为是一道很难的题呢，写了马拉车，调了好久才调出来。我保证我的做法绝对新颖，时间复杂度和空间复杂度都是 $O(N)$。

思路

看到题目，不难想到马拉车。但是又多了一个条件：

每个字符的出现次数不超过 $2$。

但这样也很简单，在向外延伸时多判断一个条件即可。

算法详解

算法由来

在求解最长回文子串的问题时，一般的思路是以当前字符为中心，向其左右两边扩展寻找回文，但是这种解法的时间复杂度是 $O(N^2)$，那么能不能将时间复杂度再降低一点？做到线性？马拉车算法就完美地解决了这个问题。

说人话就是把时间复杂度降低为 $O(N)$。

预处理

回文字符串以其长度来分，可以分为奇回文（其长度为奇数）、偶回文（其长度为偶数），一般情况下需要分两种情况来寻找回文，马拉车算法为了简化这一步，对原始字符串进行了处理，在每一个字符的左右两边都加上特殊字符（肯定不存在于原字符串中的字符），让字符串变成一个奇回文。例如：

• 原字符串：abba，长度为 $4$。

• 预处理后：XaXbXbXaX，长度为 $9$。

• 原字符串：aba，长度为 $3$。

• 预处理后：XaXbXaX，长度为 $7$。

注：X 为特殊字符，以后使用美元符号。

做法

在预处理后，先看是否超出边界 $R$，如果超出，就直接暴力向外扩展；如果没有，就先借鉴 $i$ 对于 $M$ 的中心点 $k$ 所可以扩展的最长半径，然后再暴力向外扩展。（这里还要向外扩展的原因是，可能 $k$ 在边上，无法向左或向右扩展。）

如果扩展最长半径已经超出边界，就更新边界的值。

最后打擂即可。

注意最后输出的是 $ans-1$，原因是里面加了特殊符号，导致原来长度变为原先的 $2$ 倍再加 $1$，而打擂求的是半径，因此直接减 $1$ 即可。

模板

下面给出求最长回文串长度的例题和代码。

题目：P3805 【模板】manacher。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 11000002;
// n 代表一开始字符串的长度
// m 代表添加特殊符号后的字符串的长度
// p[i] 代表往一边能够扩展的字符数即为从 i 开始的最大回文半径 
int n, m, p[N * 2 + 2];
// s[] 代表一开始的字符串
// t[] 代表添加特殊符号后的字符串 
char s[N + 2], t[N * 2 + 3];
// 马拉车 
inline void manacher() {
	n = strlen(s + 1);
	m = 0;
	// 添加特殊符号 
	t[++m] = '$';	
	for(int i = 1; i <= n; i++) {
		t[++m] = s[i]; t[++m] = '$';
	}
	int M = 0, R = 0;
	for(int i = 1; i <= m; i++) {
		// k 是 i 对于 M 的对称点 
		int k = M * 2 - i;
		if(i > R) p[i] = 1;
		else p[i] = min(p[k], R - i + 1);
		// 暴力向外扩展 
		while(i - p[i] > 0 && i + p[i] <= m && t[i - p[i]] == t[i + p[i]])
			++p[i];
		if(i + p[i] - 1 > R) M = i, R = i + p[i] - 1;
	}
}
int main() {
	// 从 1 开始读入 
	scanf("%s", s + 1);
	manacher();
	int ans = 0;
	for(int i = 1; i <= m; i++) ans = max(ans, p[i]);
	printf("%d", ans - 1);
	return 0;
}

AC 记录：link

小结

小结

马拉车算法将求解最长回文子串的时间复杂度降低到了 $O(N)$，虽然也牺牲了部分空间，其空间复杂度为 $O(N)$，但是其算法的巧妙之处还是值得学习和借鉴的。

这道题我感觉还可以枚举形态做，但是用马拉车进行求解复杂度是惊人的 $O(N)$。

个人认为这种算法应该叫条件马拉车，在朴素马拉车的基础上增加了一个条件。

本题代码

先放 AC 记录啦~

AC 记录：link

#include <bits/stdc++.h>
#define N 50010
using namespace std;
// n 代表一开始字符串的长度
// m 代表添加特殊符号后的字符串的长度
// p[i] 代表往一边能够扩展的字符数即为从 i 开始的最大回文半径 
// cnt[] 代表每个字母出现的次数
int n, m, p[N * 2 + 2], cnt[30];
// s[] 代表一开始的字符串
// t[] 代表添加特殊符号后的字符串 
char s[N + 2], t[N * 2 + 3];
// 马拉车 
inline void manacher() {
	n = strlen(s + 1);
	m = 0;
	// 添加特殊符号 
	t[++m] = '$';
	for(int i = 1; i <= n; i++) {
		t[++m] = s[i];
		t[++m] = '$';
	}
	int M = 0, R = 0;
	for(int i = 1; i <= m; i++) {
		// 每次需要清空数组
		memset(cnt, 0, sizeof(cnt));
		// k 是 i 对于 M 的对称点 
		int k = M * 2 - i;
		if(i > R) {
			p[i] = 1;
			// 本身记一次数
			if(t[i] != '$') {
				cnt[ t[i] - 'a' ] = 1;
			}
		}
		else {
			p[i] = min(p[k], R - i + 1);
			// 将之前的数据搬运过来
			for(int j = i - p[i] + 1; j <= i + p[i] - 1; j++) {
				if(t[j] != '$') cnt[ t[j] - 'a' ]++;
			}
		}
		// 暴力向外扩展，记得多加了一个条件
		while(i - p[i] > 0 && i + p[i] <= m && (t[i - p[i]] == t[i + p[i]])) {
			if(t[i - p[i]] == '$') {
				++p[i];
			}else {
				// 注意要先判断，再让 p[i] 自增，否则 p[i] 的值会改变
				cnt[ t[i - p[i]] - 'a' ] += 2;
				if(cnt[ t[i - p[i]] - 'a' ] <= 2){
					++p[i];	
				}else break; // 否则就不可以继续延伸了，跳出循环	
			}	 
		}	
		// 更新边界
		if(i + p[i] - 1 > R) M = i, R = i + p[i] - 1;
	}
}
int main() {
	// 从 1 开始读入 
	scanf("%s", s + 1);
	manacher();
	int ans = 0;
	for(int i = 1; i <= m; i++) {
		ans += p[i] / 2;
		// 直接除以二下取整得到半径
	}
	printf("%d", ans);
	return 0;
}