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 算法学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享