Manacher 算法学习笔记

2022/2/14 12:11:49

本文主要是介绍Manacher 算法学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Manacher 算法是一种支持在 \(O(n)\) 时间内求出一个长度为 \(n\) 的字符串的最长回文子串的算法。

需要注意的是,Manacher 算法只能求形如 \(aabbcbbaa\) 类的回文串,而不能处理形如 \(aabbbbaa\) 类的回文串,也就是只能求长度为奇数的回文串。所以,在最初需要对原串进行预处理,用没有出现过的字符将原串中的相邻两个字符隔开,同时要用两个不同的字符分别放在原串的开头和结尾。
如原串为 \(abbcac\),转化后就可以是 $#a#b#b#c#a#c#^。此时再和原串中的回文子串一一对应,会发现原串的回文串长度就是新串的回文串半径的长度减一。

回到 Manacher 算法,它本身的思想是从前往后一个个递推,求出 \(p[i]\) 表示以 \(s_i\) 为中心的最长回文串的半径长度。而 \(\max(s_i-1)\) 自然就是答案。(下文简记回文子串 \(s_i\) 表示以 \(s_i\) 为中心的最长回文子串)

从前往后递推的时候,维护一个右边界最靠右的回文子串,记为 \(maxright\),简称 \(mr\),而回文子串的中心就被称为 \(mid\)。
由于这个回文子串是在 \(i\) 之前枚举到的,所以必然有 \(mid<i\)。但是 \(i\) 和 \(mr\) 的大小关系就是不确定的,需要分情况讨论。

\(1\). \(i \leq mr\)。由于此时 \(i\) 在回文子串 \(mid\) 内,那么就可以在这个回文子串中找到 \(i\) 的对称点,记为 \(j\),那么根据简单的数学知识,可知 \(j=2*mid-i\)。

(1).\(j-p[i]+1 \geq 2*mid-mr\),即 回文子串 \(j\) 完全在回文子串 \(mid\) 内,那么根据回文子串内部 \(mid\) 左右两边对称的性质,就有 \(p[i]=p[j]\)。如果此时恰好 \(i+p[j]-1\) 取到 \(mr\),那么就无法保证 \(i+p[j]\) 是否与 \(i-p[j]\) 相等,因此是 \(p[i] \geq p[j]\)。

(2).\(j-p[i]+1 \geq 2*mid-mr\),即回文子串 \(j\) 的一部分前缀不在回文子串 \(mid\) 内。此时一定满足 \(p[i] \leq mr\)。证明如下图所示:

可以推出最左边和最右边的红色部分的子串对称,这与 \(mr\) 是回文子串 \(mid\) 的右边界矛盾。故一定有 \(p[i] \leq mr\)。但是根据回文子串 \(i\) 与左边的回文子串 \(j\) 对称,只能是 \(p[i]=mr-i+1 <p[j]\)。

综上,当 \(i \leq mr\) 时,有 \(p[i] \geq \min(p[j],mr-i+1)\)。

\(2\).\(i >mr\)。此时回文子串 \(i\) 就有可能很大。直接从 \(p[i]=1\) 开始枚举即可。

综合以上两种情况,我们先求出 \(p[i]\) 的下界,并不断往外拓展,直到不能扩展为止。如果此时 \(i+p[i]-1 > mr\),就需要更新 \(mid\) 和 \(mr\)。

下面来简单证明一下为什么这样做的时间复杂度是 \(O(n)\)。在情况 \(1\) 中,只有当 \(j-p[j]+1\) 恰好与 \(2*mid-mr\) 相等时扩展操作会执行多次。那么此时的 \(mid\) 就会更新成 \(i\),实际上也就是 \(mr\) 在单调递增。而情况 \(2\) 也是如此,故扩展操作最多执行 \(O(n)\) 次。那么复杂度也就稳定在 \(O(n)\)。

code:

#include<cstring>
#include<algorithm>
using namespace std;
const int N=32000005;
int ans,n,p[N];char a[N],b[N];
void init()
{
	int k=0;b[k++]='$',b[k++]='#';
	for(int i=0;a[i];i++) b[k++]=a[i],b[k++]='#';
	b[n=k]='^';//$和^主要是防止边界问题,如果不想加也可以在while循环里特判一下 
}
void manacher()
{
	int mr=0,mid;//在代码实现中,通常会将mr定义为最长回文子串最右边再过去一个字符的下标,因此下面部分代码与思路有所不同 
	for(int i=1;i<=n;i++)
	{
		if(i<mr) p[i]=min(mr-i,p[2*mid-i]);
		else p[i]=1;
		while(b[i+p[i]]==b[i-p[i]]) p[i]++;
		if(i+p[i]>mr) mr=i+p[i],mid=i;
		ans=max(ans,p[i]-1);
	}
}
int main()
{
	scanf("%s",a);init();manacher();printf("%d\n",ans);
	return 0;
}```


这篇关于Manacher 算法学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程