首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

算法·理论:Manacher 笔记

编程知识
2024年08月05日 20:19

\(\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\)(即可以利用是以前的信息),那么:

\[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\) 开始暴力中心扩展即可。

\(\bf{Manacher}\) 复杂度

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

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

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

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

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


累啊!不过如此!

From:https://www.cnblogs.com/godmoo/p/18344077
本文地址: http://www.shuzixingkong.net/article/821
0评论
提交 加载更多评论
其他文章 【Playwright+Python】系列教程(七)使用Playwright进行API接口测试
playwright也是可以做接口测试的,但个人觉得还是没有requests库强大,但和selenium相比的话,略胜一筹,毕竟支持API登录,也就是说可以不用交互直接调用接口操作了。 怎么用 既然是API的测试了,那肯定就别搞UI自动化那套,搞什么浏览器交互,那叫啥API测试,纯属扯淡。 也不像有
【Playwright+Python】系列教程(七)使用Playwright进行API接口测试 【Playwright+Python】系列教程(七)使用Playwright进行API接口测试 【Playwright+Python】系列教程(七)使用Playwright进行API接口测试
架构演化学习思考(4) --- IOC的学习认识
架构演化学习思考(4) IOC的学习认识 IOC相关概念认识 什么是IOC? IOC全称为 Inversion Of Control ,即控制反转。它是一种控制思想,可以解释为类和类之间的依赖关系不再由代码直接控制,而是通过容器来控制和配置实现。 控制反转?那么什么是正传? 反转有啥好处?IOC到底
架构演化学习思考(4) --- IOC的学习认识 架构演化学习思考(4) --- IOC的学习认识 架构演化学习思考(4) --- IOC的学习认识
在oracle中将一行字符串拆分成多行
例如,有如下一张表,表名为bk_test。插入了以下数据: CREATE TABLE BK_TESK(id varchar2(10),s varchar2(20)); insert into BK_TESK values (&#39;A&#39;,&#39;1,2,3&#39;); insert i
在oracle中将一行字符串拆分成多行 在oracle中将一行字符串拆分成多行
代码随想录Day5
242.有效的字母异位词 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。 示例 1: 输入: s = &quot;anagram&quot;, t = &quot;nagaram&
数据结构 顺序与链式二叉树的原理与实现(万字)
目录一、树概念及结构树的概念树的相关概念树的表示二、二叉树概念及结构概念特殊的二叉树二叉树的性质二叉树的存储结构三、二叉树的顺序结构及实现二叉树的顺序结构堆的概念及结构堆的实现堆向下调整算法堆的创建建堆时间复杂度堆的插入堆的删除堆的代码实现Heap.hHeap.c堆的应用堆排序堆排序代码实现Heap
数据结构 顺序与链式二叉树的原理与实现(万字) 数据结构 顺序与链式二叉树的原理与实现(万字) 数据结构 顺序与链式二叉树的原理与实现(万字)
在Vue3中如何为路由Query参数标注类型
与以往的OOP或者Class方案不同,Zova在界面交互层面仍然采用Setup语法,仅仅在业务层面引入IOC容器。IOC容器犹如一把钥匙,为我们打开了业务工程化的大门,允许我们探索更多工程化方面的设计和能力。
在Vue3中如何为路由Query参数标注类型 在Vue3中如何为路由Query参数标注类型 在Vue3中如何为路由Query参数标注类型
selenium复习之---原理+基础用法
简介 1.是什么 selenium是用来进行页面元素定位的第三方库,用来进行web自动化测试的工具,可以直接运行在浏览器中。 2.原理: selenium在工作过程中有三个角色,selenium客户端、webdriver和浏览器 selenium客户端是开发者与selenium的交互接口,它会发送指
.NET电子邮件高效处理解决方案
前言 在日常软件开发中,电子邮件处理是一个不可或缺的功能,无论是用户注册验证、通知推送还是日常的业务沟通,都离不开电子邮件的支持。今天大姚给大家分享2款.NET开源、高效、强大的.NET电子邮件处理库,这些库不仅简化了电子邮件的发送、接收和管理工作,还提供了丰富的功能和灵活的配置选项,以满足各种复杂