学习笔记/String：Manacher 笔记

2024-08-05 21:19 由 godmoo 发表于 #其他

BASIC INFORMATION

TOPIC: \(\small\text{Manacher}\) 算法。

REFERENCE: 基本说明和常用符号参考字符串系列目录&&说明。

UPDATE:
\(\small\text{2024-8-6}\)，重修文章格式。
\(\small\text{2024-8-7}\)，更改文章表示，更加易懂。

\(\text{Manacher}\) 来啦！

\(\text{Manacher}\) 并没有什么前置知识，比 \(\text{KMP}\) 简单多了。

前置处理

\(\text{Manacher}\) 算法用于解决回文串相关的问题，先看几个与回文串相关的基本概念：回文中心、回文半径。

打个形象的比方，如果将一个回文串比作一个轴对称图形的话，那么回文中心就是对称轴，回文半径就是回文中心与右（左）端点的距离。比如说回文串 \(\texttt{abcba}\) 的回文中心就是中间的 \(\texttt{c}\)，回文半径就是 \(3\)，算上回文中心。

还有一个重要问题：对于回文串，有长度为奇数或长度为偶数之分，即奇回文串和偶回文串。显然两种回文串需要分开进行处理，因为奇回文串的回文中心是一个字符，但偶回文串的回文中心是在两个相邻字符之间的，那我们看看能不能一致处理。

不难想到，既然偶回文串的的回文中心在两个相邻的字符之间，那我们不妨往每两个相邻字符之间插入一个虚拟的字符，比如 \(\texttt{\#}\)。

比如说对于偶回文串 \(\texttt{abba}\)，我们将他成 \(\texttt{\#a\#b\#b\#a\#}\)，这样这个偶回文串就变成了一个奇回文串，它的回文中心就变成 \(\texttt{\#}\) 了！现在所有回文串都变成奇回文串了，接下来我们就可以一致处理了。

（至于头尾为何各放一个，后文再讲）

Manacher 算法

\(\text{Manacher}\) 算法，可以在 \(O(n)\) 的复杂度下处理出以每个字符（或两个字符之间）为回文中心的最大回文半径 \(rad[]\)。

先明确一下回文半径的定义：如果这个回文串的回文中心为 \(o\)，右端点为 \(r\)，那么这个回文串的回文半径 \(rad=r-o+1\)，也就是说回文半径要算上回文中心。

那么我们开始吧！首先思考朴素做法，显然我们可以枚举回文中心，再不断同时往两边扩展，扩展到不同时就找到了最远的左、右端点了，这个算法叫做中心扩展算法，时间复杂度 \(O(n^2)\)，这里给出实现：

// force.cpp
int n,s[N],rad[N];
prepare(); // 用前面说的方式统一奇、偶回文串 
for(int i=1;i<=n;i++){
	rad[i]=1;
	while(s[i-rad[i]]==s[i+rad[i]]) rad[i]++;
}

同样注意到我们可以在此基础上二分回文半径 \(rad[i]\)，接着用子串哈希 \(O(1)\) 比较，时间复杂度降到 \(O(n\log n)\)。

回忆我们的 \(\text{KMP}\) 算法是如何优化时间复杂度的：重复利用已知的信息，我在 \(\text{KMP}\) 的文章中提过，这种思想叫做增量法，同时这也是 dp 思想的体现。

那我们考虑有什么信息可以重复利用？那显然是回文啊！那回文又有什么性质呢？对称啊！所以发现如果我们之前已经扩展到这个字符过，那前面就一定有和当前的字符对称的内容，那该字符显然也会拥有前面与它对称的字符的回文半径。

比如说字符串 \(s=\texttt{babcbab}\)，当我们枚举到 \(s[6]\) 时（倒数第二个字符 \(\texttt{a}\)），显然这里已经被 \(s[4]\)（中间的 \(\texttt{c}\)）扩展过。由中点公式，与它对称的字符是 \(s[2\times 4-6]=s[2]\)，显然我们前面已经处理出 \(rad[2]\) 了，\(rad[2]=2\)，所以 \(rad[6]\) 就至少为 \(2\) 了，当然还需要从回文半径为 \(3\) 开始继续拓展。

但注意到我们只是对称到了前面计算过的点，并不保证能完全对称到整个回文子串，比如说对于字符串 \(t=\texttt{babcbad}\)，在枚举到 \(s[6]\) 时（倒数第二个字符 \(\texttt{a}\)），虽然可以通过之前 \(s[4]\)（中间的 \(\texttt{c}\)）对称到 \(s[2\times 4-6]=s[2]\)，但是 \(rad[6]\) 却不能到 \(rad[2]\)（自己看一下是不是），为什么呢？

因为虽然回文中心可以对称过来，但是 \(s[4]\) 的 \(rad\) 不够长，\(s[7]\) 无法对称过去，所以这样做就无法保证整个回文串都能对称过去，解决方法就是只能利用以 \(s[4]\) 为回文中心的最长回文串的右端点以内的信息，也就是说 \(rad[6]\) 不能直接等于 \(rad[2]\)，还要跟在以 \(s[4]\) 为回文中心的最长回文串的右端点以内的可扩展的最长长度取 \(\min\)。

形式化的，设我们所利用的回文串的回文中心为 \(o\)，右端点为 \(r\)，现在枚举到 \(s[i]\) 且 \(s[i]<r\)（即可以利用是以前的信息），那么：

\[rad[i] \leftarrow\min(rad[2o-i],r-i+1) \]

接着继续中心扩展即可。

解释：\(\min\) 的一个参数是对称过去的字符所对应的 \(rad\)，由中点公式得到；而 \(\min\) 的第二个参数是在 \(r\) 及以内的可以扩展的最长长度，相信经过前面的讲解你应该也懂了。

那在枚举的过程中同时不断更新 \(o\) 和 \(r\) 即可。

看一眼代码：

int n;
char a[N],s[N<<1];
void manacher(){
	//  特殊处理
	int cur=0;
	s[0]='@';
	s[++cur]='#';
	for(int i=1;i<=n;i++) s[++cur]=a[i],s[++cur]='#';
	s[++cur]='!';
	n=cur-1;
	// 接下来就可以一致处理了
	for(int i=1,o=0,r=0;i<=n;i++){
		rad[i]=(i>r?1:min(rad[(o<<1)-i],r-i+1)); // 利用之前的信息
		while(s[i-rad[i]]==s[i+rad[i]]) rad[i]++; // 中心扩展
		if(i+rad[i]-1>r) o=i,r=i+rad[i]-1; // 更新 o 和 r
	}
}

a 是原串，s 是处理过后的字符串。

先说怎么算实际原串的以 \(i\) 为回文中心的最长回文串的长度，其实就是 \(rad[i]-1\)（因为特殊处理后加了字符 \(\texttt{\#}\)），自己分类讨论一下 \(s[i]\) 是或不是 \(\texttt{\#}\)，就容易推出这个式子了。

接着我们就可以解答上文的问题了，为什么头尾要各加一个 \(\texttt{\#}\)？举个例子，对于字符串 \(\texttt{bac}\)，其实应转换为 \(\texttt{\#b\#a\#c\#}\)，那么在枚举到 \(\texttt{a}\) 时，实际上得到的回文串是 \(\texttt{\#a\#}\)，所以对于头尾的字符我们也应该做相同处理，于是前后各加一个 \(\texttt{\#}\)；或者你想想，如果两边不不加，那么 \(rad=1\)，于是以它为回文中心的最长回文串的长度就为 \(rad-1=1-1=0\) 了，所以要这样修正。

那为什么头尾还要加 \(\texttt{@}\) 和 \(\texttt{!}\) 呢？是为了防止越界，或者说让扩展整个串的左右端点处停下来，比方说整个串就对称时，若枚举它的回文中心，那如果不往两边加两个不同的字符，那就会一直扩展下去，那就越界了。

其他的就没有什么好说的了，注意当 \(i>r\) 时就直接从 \(1\) 开始暴力中心扩展即可。

Manacher 的复杂度

首先答案肯定是 \(O(n)\) 的，~~依据是字符串算法全是线性的~~。

\(\text{KMP}\) 知道怎么分析了，那就自己想想吧，答案在下面。

\(\color{white}\text{同样唯一需要分析的就是这个 while,其他都显然是 O(n) 的。}\)

\(\color{white}\text{每个字符至多被从它后面暴力扩展到它一次，所以只会进行 O(n) 次 while。}\)

\(\color{white}\text{综上，实际复杂度 O(n)。}\)

累啊！不过如此！