首页 > 极客资料 博客日记
算法·理论:Manacher 笔记
2024-08-05 21:30:04极客资料围观30次
\(\text{Manacher}\) 来啦!
\(\text{Manacher}\) 并没有什么前置知识,比 \(\text{KMP}\) 简单多了。
前置处理
\(\text{Manacher}\) 算法用于解决回文串相关问题,先看几个基本概念:回文中心、回文半径,这些看字面意思就能猜到。
还有一个重要问题:对于回文串,有长度为奇数或长度为偶数之分,即奇回文串和偶回文串。显然两种回文串需要分开进行处理,因为奇回文串的回文中心是一个字符,但偶回文串的回文中心是在两个相邻字符之间的,那我们看看能不能一致处理。
不难想到,既然偶回文串的的回文中心在两个相邻的字符之间,那我们不妨往每两个相邻字符之间插入一个虚拟的字符,比如 \(\texttt{\#}\)。
比如说对于偶回文串 \(\texttt{abba}\),我们将他成 \(\texttt{\#a\#b\#b\#a\#}\),这样这个偶回文串就变成了一个奇回文串,它的回文中心就变成 \(\texttt{\#}\) 了!现在所有回文串都变成奇回文串了,接下来我们就可以一致处理了。
(至于头尾为何各放一个,后文再讲)
\(\bf{Manacher}\) 算法
\(\text{Manacher}\) 算法,可以在 \(O(n)\) 的复杂度下处理出以每个字符(或两个字符之间)为回文中心的最大回文半径 \(rad[]\)。
先说明一下回文半径的定义:如果这个回文串的回文中心为 \(o\),右端点为 \(r\),那么这个回文串的回文半径 \(rad=r-o+1\),也就是说回文半径要算上回文中心。
那么我们开始吧!首先思考朴素做法,显然我们可以枚举回文中心,再不断同时往两边扩展,扩展到不同时就找到了最远的左、右端点了,这个算法叫做中心扩展算法,时间复杂度 \(O(n^2)\),代码就不放了,很好打。
同样注意到我们可以在此基础上二分回文半径,接着用子串哈希 \(O(1)\) 比较,时间复杂度降到 \(O(n\log n)\)。
会议我们的 \(\text{KMP}\) 算法是如何优化时间复杂度的:重复利用已知的信息,我在 \(\text{KMP}\) 的文章中提过,这种思想叫做增量法,同时这也是 dp 思想的体现。
那我们考虑有什么信息可以重复利用?那显然是回文啊!那回文又有什么性质呢?对称啊!所以发现如果我们之前已经扩展到这个字符过,那前面就一定有和当前的字符对称的内容,那该字符显然也会拥有前面与它对称的字符的回文半径。
比如说字符串 \(s=\texttt{babcbab}\),当我们枚举到 \(s[6]\) 时(倒数第二个字符),显然这里已经被 \(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]\) 时(倒数第二个字符),虽然可以通过之前 \(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\)(即可以利用是以前的信息),那么:
接着继续中心扩展即可。
解释:\(\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\) 开始暴力中心扩展即可。
\(\bf{Manacher}\) 复杂度
首先答案肯定是 \(O(n)\) 的,依据是字符串算法全是线性的。
\(\text{KMP}\) 知道怎么分析了,那就自己想想吧,答案在下面。
\(\color{white}\text{同样唯一需要分析的就是这个 while,其他都显然是 O(n) 的。}\)
\(\color{white}\text{每个字符至多被从它后面暴力扩展到它一次,所以只会进行 O(n) 次 while。}\)
\(\color{white}\text{综上,实际复杂度 O(n)。}\)
累啊!不过如此!
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”