基本概念

\(manacher\) 算法是一种 字符串算法，通常用于求解给定的字符串 \(S\) 内最长的回文子串长度。其充分利用了回文串的 对称性，可以在 \(O(n)\) 的时间复杂度内求出最长回文子串。\(manacher\) 算法的主要思路和 \(KMP\) 算法类似，都是通过已经求出的子串信息来加速暴力枚举的过程。

算法思想

\(manacher\) 算法通过回文的对称性来确定出一部分已经确定的回文子串，从而减少枚举的长度，达到线性的时间复杂度。当然，在对字符串进行 \(manacher\) 算法之前需要对字符串进行处理。

首先考虑最暴力的做法：枚举 \(0 \leq i < n\)​，将下标 \(i\)​ 作为可能的回文子串中点。用双指针向两端扩展，遇到不同的字符退出。这样做需要分类讨论回文子串长度为 奇数 和回文子串长度为 偶数 的情况，并且最坏情况下对于每一个 \(i\) 都需要扫描一遍字符串。时间复杂度为 \(O(n^2)\)。

为了避免分类讨论，我们考虑在每个字符的首尾都增加一个没有在字符串 \(S\)​​​​​ 中出现过的字符。例如当字符串 \(S = \texttt{texas}\)​​​​​ 时，在每个字符的首位都增加一个字符 \(\texttt{#}\)​​​​​​ 以后，最终的字符串 \(S^{\prime} = \texttt{#t#e#x#a#s#}\)​​​​​ 。这时我们发现字符串 \(S\)​​ 中的回文子串无论长度奇偶，在字符串 \(S^{\prime}\)​​ 对应的字符串长度一定为奇数。

对于优化过暴力的 \(manacher\) 算法，为了减少对边界的判断，我们再在字符串的开头加上另一个没有字符串中出现过的字符。最终的字符串 \(S^{\prime\prime}\) 可能会是 \(\texttt{|#t#e#x#a#s#}\)。具体的原因参见下文。为方便起见，下文出现的字符串 \(S\) 全部指代此处的字符串 \(S^{\prime\prime}\)​。

定义 \(len_i\)​​​​ 表示字符串 \(S\)​​​​ 以下标 \(i\)​​​​ 为回文子串中点时的最长回文子串长度半径。例如 \(S = \texttt{|#a#b#a#b#a#}\)​​​​ 时 \(len_6 = 6\)​​​​，对应回文子串 \(\texttt{#a#b#a#b#a#}\)​​​​​。假设字符串 \(S\)​​​​ 内中点在 \([0, i - 1]\)​​​ 区间内最靠右且最长的回文子串为 \(a\)​​​​，设 \(a\)​​​​ 的中点为 \(p\)​​​​，\(a\)​​​​ 的右端点在 \(S\)​​​​ 中的下标为 \(r\)​​​​。此时我们考虑能否直接从 \([len_0, len_{i - 1}]\)​​​​ 中贡献一部分确定的回文子串，减少枚举量。此时稍微分类讨论。

假如 \(i > r\)​，那么因为以 \(i\)​ 为中点的最长回文子串一定会包含 \(S_{0, i}\)​ 以外的部分，所以无法直接从 \([len_0, len_{i - 1}]\)​​​ 转移，考虑暴力双指针枚举。反之，若 \(i \leq r\)，那么我们可以先确定一部分回文子串。因为 \(i\) 被包含在某一个回文子串内，所以在该回文子串 \(a = [S_l, S_r]\) 内一定存在一个回文子串，使得这个回文子串是以 \(i\) 为中点的回文子串的子串。

结合一个例子来理解。不妨设 \(S = \texttt{|#t#e#x#e#x#}\)​​​​​​​​，假设现在要更新 \(len_8, S_8 = \texttt{e}\)​​​​​​​​。此时 \(p = 6, r = 9\)​​​​​​。因为 \(8 < 9\)​​​​​，所以可以考虑先确定一部分回文子串。我们发现因为 \(i\)​​​​​ 被包含在回文子串内，所以在区间 \([i - len_i + 1, i + len_i - 1]\)​​​​ 内一定存在至少两个 \(S_i\)​​​，并且 \(S_i = S_{2 \times p - i}\)​​​。具体到这个例子也就是在 \(4\)​​​ 的位置一定为 \(\texttt{e}\)​​​。这时 \(len_{2 \times p - i}\)​​​​ 一定已经计算过了，并且由于位置 \(i\)​​ 也在目前最右侧的最长回文子串内，所以位置 \(i\)​​ 的回文子串一定包含长度为 \(len_{2 \times p - i} \times 2 - 1\)​​ 的与位置 \(2 \times p - i\)​​​ 的回文子串相同的子串。我们还需要考虑溢出，假如 \(len_{2 \times p - i}\)​​ 过大，延伸到了右侧最长回文子串的右边，那么因为我们没有计算右边的值，所以不能用这个值来更新。那么因为 \(i + len_{2 \times p - i} > r, 2 \times p - i - len_{2 \times p - i} < l\)​​，所以回文子串一定可以包含 \(S_{i, r}\)​​。因此当 \(i \leq r\)​​ 的时候，可以确定的回文子串长度最大为 \(\min\{len_{2 \times p - i}, r - i + 1\}\)​。

从确定的回文子串两侧开始延伸双指针，直到遇到不同的字符为止。因为在循环的过程中最右侧最长回文子串的右端点是不降的，如果当前回文子串的右端点不超过右侧最长回文子串​的右端点，那么直接转移的时间复杂度显然是 \(O(1)\)​。如果超过，则此时右侧最长回文子串的右端点一定会增加。右端点右移的时间复杂度为 \(O(n)\)​​。因此 \(manacher\)​ 算法的时间复杂度为 \(O(n)\)​。

在代码实现的时候，存储 \(len\) 时不必过多判断边界。这里可以不用 \(- 1\)，相应地代码中也有一些需要更改的地方。下面的模板字符串下标从 \(0\) 开始，因此边界条件的判断是对的。

参考代码

例题链接

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1.1e7 + 5;

int n, cnt, ans;
int len[maxn * 3];
char a[maxn], s[maxn * 3];

void get_str()
{
	s[cnt] = '#';
	s[++cnt] = '|';
	for (int i = 0; i < n; i++)
	{
		s[++cnt] = a[i];
		s[++cnt] = '|';
	}
}

int main()
{
	int r = 0, mid = 0;
	scanf("%s", a);
	n = strlen(a);
	get_str();
	for (int i = 1; i <= cnt; i++)
	{
		if (i <= r)
			len[i] = min(len[2 * mid - i], r - i + 1);
		while (s[i - len[i]] == s[i + len[i]])
			len[i]++;
		if (len[i] + i - 1 >= r)
		{
			r = len[i] + i - 1;
			mid = i;
		}
		ans = max(ans, len[i]);
	}
	printf("%d\n", ans - 1);
	return 0;
}