Manacher 算法学习笔记

算法介绍

Manacher 是一个求解字符串的回文子串的算法。

考虑这样的一道例题：

给定字符串 $S$ ，询问所有子串中的最长回文子串长度。例如
ebaabaf 最长的回文子串是 baab。

$1\le|S|\le 1.1\times 10^7$ 。

很明显能使用中心点和往一端拓展的长度来确定一个回文子串，但由于回文串分为奇回文串和偶回文串，而奇回文串的中心是字符，偶回文串的中心确是字符的间隔处，所以可以在两个字符中间加入 #，来使得所有回文子串都变为奇回文串。

例如字符串 dbaabab 就变成了 #d#b#a#a#b#a#b#；

原串中的回文子串 aba 对应转化串中的 #a#b#a#；

原串中的回文子串 baab 对应转化串中的 #b#a#a#b#。

这样一来，奇/偶回文子串的中心都在字符上。只不过，奇回文子串的中心在转化串里是原串的字符；而偶回文子串的中心在转化串里是 # 间隔符。

但是这样一来，同一个回文子串我们就会计算两遍，因为 a#b#a 和 #a#b#a# 都对应原串中的 aba。所以如果一个字符作为中心在转化串中最多能扩展 $L$ 位，那么在原串中它最多只能拓展 $\lfloor \dfrac{L}{2}\rfloor$ 位。

预处理完转换串后，我们就可以开始求解答案了。设 $ext_i$ 表示从第 $i$ 位开始拓展，最多可以拓展的位数。即满足 $S_{i-ext_i}\ne S_{i+ext_i}$ 的最小的值。（注意是在转换串上）

首先考虑暴力求解。可以枚举每一个 $i$ ，然后往两边暴力拓展，直到遇到不同的字符。

但我们考虑以下这种情况：

求以 xyzdabaaabaefeaba[a]abadxyz 中被框起来的字符 a 为回文中
心的最长回文子串。

假如我们知道

xyz [dabaaabaefeabaaabad] xyz

和

xyz d[abaaaba]efeabaaabad xyz

被框起来的部分都是回文子串，那么我们就可以得出需要求解的回文子串至少包含下面被框起来的部分：

xyz dabaaabaefe[abaaaba]d xyz

这条特质是由回文串的对称性引出的，也就是说被大回文串包含的小回文串可以以大回文串中心“对过去”。

所以转移过程中，我们需要记录下对于当前的 $i$ ，以 $pos$ 为中心的回文子串中，右端点最靠右的那个 $pos$ ，即找到 $pos+ext_{pos}$ 最大的 $pos$ 。（ $1\le pos\le i-1$ ）

如果 $pos+ext_{pos}> i$ ，那么 $i$ 在 $pos$ 为中心的最长回文子串内，直接让 $ext_i=\min(ext_{pos}+pos-i,ext_{pos*2-i})$ 然后暴力拓展即可。
否则直接暴力拓展

最后更新一下 $pos$ 即可。

然后还有一个很重要的细节，为了防止算法跑出去，所以要在转化串开头和结尾分别加上 @ 和 & 两个哨兵。

模板代码：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n;
char s[30000005];
int ext[30000005];

int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	// 预处理转化串 
	for(int i=n;i>=1;i--)
	{
		s[i*2]=s[i];
	}
	n=n*2+1;
	for(int i=1;i<=n;i+=2)
	{
		s[i]='#';
	}
	// 加入哨兵 
	s[0]='@';
	s[n+1]='&';
	int ans=0;
	for(int i=1,pos=0;i<=n;i++)
	{
		if(pos+ext[pos]>i) ext[i]=min(pos+ext[pos]-i,ext[pos*2-i]); // 运用特质拓展 
		while(s[i+ext[i]]==s[i-ext[i]]) ext[i]++; // 暴力拓展 
		if(i+ext[i]>pos+ext[pos]) pos=i; // 更新 pos 
		ans=max(ans,ext[i]-1);
	}
	printf("%d\n",ans);
	return 0;
}

时空复杂度分析

空间复杂度

显然是 $O(n)$ 的，但是注意要开两倍空间。
时间复杂度

考虑 $r=pos+ext_{pos}$ 在算法过程中的变化，分为两种情况：
- 当前的 $i$ 运用特质拓展了：
  
  此时要么 $i$ 不会再暴力拓展，要么是这种情况：
  
  这样每暴力拓展一次 $r$ 就一定会往右移一位。
- 当前的 $i$ 未运用性质拓展，那么每暴力拓展一次 $r$ 就一定会往右移一位。
最后我们得到了一个结论：每次暴力拓展都会令 $r$ 右移一位，那么暴力拓展的次数上限是 $n$ ，算法时间复杂度自然为 $O(n)$ 。

注意到每次暴力拓展都有可能是找到了一个新的回文子串，所以一个字符串 $S$ 的本质不同回文子串个数最多是 $n$ 。