【算法知识总结】最长回文子串-Manacher算法

2024-06-03 01:38

本文主要是介绍【算法知识总结】最长回文子串-Manacher算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

转载自:《简书》曾会玩-最长回文子串问题—Manacher算法
问题说明
最长回文子串问题:给定一个字符串,求它最长回文子串长度。

  1. 方法比较

    Brute-force解法
    对于最长回文子串问题,最简单粗暴的办法是:找到字符串的所有子串,遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定,因此对于一个长度为 n n 的字符串,共有n2个子串。这些子串的平均长度大约是 n/2 n / 2 ,因此这个解法的时间复杂度是 O(n3) O ( n 3 )
    .
    改进的方法
    显然所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称,而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可否利用这种对称性来提高算法效率呢?答案是肯定的。我们知道整个字符串中的所有字符,以及字符间的空隙,都可能是某个回文子串的对称轴位置。可以遍历这些位置,在每个位置上同时向左和向右扩展,直到左右两边的字符不同,或者达到边界。对于一个长度为n的字符串,这样的位置一共有 n+n1=2n1 n + n − 1 = 2 n − 1 个,在每个位置上平均大约要进行 n/4 n / 4 次字符比较,于是此算法的时间复杂度是 O(n2) O ( n 2 )
    .
    Manacher 算法
    对于一个比较长的字符串, O(n2) O ( n 2 ) 的时间复杂度是难以接受的。Can we do better?
    先来看看解法2存在的缺陷。
    .
    1)由于回文串长度的奇偶性造成了不同性质的对称轴位置,解法2要对两种情况分别处理;
    .
    2)很多子串被重复多次访问,造成较差的时间效率。

  2. Manacher算法解决重复访问的问题
    我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。 Manacher定义了一个回文半径数组 RL R L ,用 RL[i] R L [ i ] 表示以第 i i 个字符为对称轴的回文串的回文半径。我们一般对字符串从左往右处理,因此这里定义RL[i]为第 i i 个字符为对称轴的回文串的最右一个字符与字符i的距离。对于上面插入分隔符之后的两个串,可以得到 RL R L 数组:

char:    # a # b # a #RL :    1 2 1 4 1 2 1
RL-1:    0 1 0 3 0 1 0i :    0 1 2 3 4 5 6char:    # a # b # b # a #RL :    1 2 1 2 5 2 1 2 1
RL-1:    0 1 0 1 4 1 0 1 0i :    0 1 2 3 4 5 6 7 8

上面我们还求了一下 RL[i]1 R L [ i ] − 1 。通过观察可以发现, RL[i]1 R L [ i ] − 1 的值,正是在原本那个没有插入过分隔符的串中,以位置 i i 为对称轴的最长回文串的长度。那么只要我们求出了RL数组,就能得到最长回文子串的长度。
于是问题变成了,怎样高效地求的 RL R L 数组。基本思路是利用回文串的对称性,扩展回文串。
我们再引入一个辅助变量MaxRight,表示当前访问到的所有回文子串,所能触及的最右一个字符的位置。另外还要记录下MaxRight对应的回文串的对称轴所在的位置,记为pos,它们的位置关系如下。
这里写图片描述

我们从左往右地访问字符串来求 RL R L ,假设当前访问到的位置为 i i ,即要求RL[i],在对应上图, i i 必然是在po右边的(obviously)。但我们更关注的是,i是在MaxRight的左边还是右边。我们分情况来讨论。
1) 当i在MaxRight的左边;
情况1)可以用下图来刻画:
这里写图片描述
我们知道,图中两个红色块之间(包括红色块)的串是回文的;并且以i为对称轴的回文串,是与红色块间的回文串有所重叠的。我们找到 i i 关于pos的对称位置j,这个 j j 对应的RL[j]我们是已经算过的。根据回文串的对称性,以 i i 为对称轴的回文串和以j为对称轴的回文串,有一部分是相同的。这里又有两种细分的情况。

a. 以j为对称轴的回文串比较短,短到像下图这样。
这里写图片描述

这时我们知道 RL[i] R L [ i ] 至少不会小于 RL[j] R L [ j ] ,并且已经知道了部分的以i为中心的回文串,于是可以令 RL[i]=RL[j] R L [ i ] = R L [ j ] 。但是以i为对称轴的回文串可能实际上更长,因此我们试着以i为对称轴,继续往左右两边扩展,直到左右两边字符不同,或者到达边界。
b. 以j为对称轴的回文串很长,这么长:
这里写图片描述

这时,我们只能确定,两条蓝线之间的部分(即不超过MaxRight的部分)是回文的,于是从这个长度开始,尝试以i为中心向左右两边扩展,,直到左右两边字符不同,或者到达边界。
不论以上哪种情况,之后都要尝试更新MaxRight和pos,因为有可能得到更大的MaxRight。
具体操作如下:

step 1: RL[i] <--- min(RL[2*pos-i], MaxRight-i)
step 2: 以i为中心扩展回文串,直到左右两边字符不同,或者到达边界。
step 3: 更新MaxRight和pos

2)当 i i 在MaxRight的右边。
这里写图片描述

遇到这种情况,说明以i为对称轴的回文串还没有任何一个部分被访问过,于是只能从i的左右两边开始尝试扩展了,当左右两边字符不同,或者到达字符串边界时停止。然后更新MaxRight和pos。
.
- 算法实现

def manacher(s):#预处理s='#'+'#'.join(s)+'#'RL=[0]*len(s)MaxRight=0pos=0MaxLen=0for i in range(len(s)):if i<MaxRight:RL[i]=min(RL[2*pos-i], MaxRight-i)else:RL[i]=1#尝试扩展,注意处理边界while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:RL[i]+=1#更新MaxRight,posif RL[i]+i-1>MaxRight:MaxRight=RL[i]+i-1pos=i#更新最长回文串的长度MaxLen=max(MaxLen, RL[i])return MaxLen-1

.
- 复杂度分析
空间复杂度:插入分隔符形成新串,占用了线性的空间大小;RL数组也占用线性大小的空间,因此空间复杂度是线性的。
时间复杂度:尽管代码里面有两层循环,通过 amortizedanalysis a m o r t i z e d a n a l y s i s 我们可以得出, Manacher M a n a c h e r 的时间复杂度是线性的。由于内层的循环只对尚未匹配的部分进行,因此对于每一个字符而言,只会进行一次,因此时间复杂度是 O(n) O ( n )

PS. 好玩儿的Facts(via. wiki)

  • 人们在一座名为赫库兰尼姆的古城遗迹中,找到了一个好玩的拉丁语回文串:sator arepo tenet opera rotas。翻译成中文大概就是`一个叫做Arepo的播种者,他用力地扶(把)着车轮。这个串的每个单词首字母刚好组成了第一个单词,每个单词的第二个字母刚好组成了第二个单词…于是乎,如果写出酱紫,你会发现上下左右四个方向读起来是一样的。这个串被称为 Sator Square.

  • 本文开头给出的单词tattarrattat,出现在爱尔兰作家詹姆斯·乔伊斯的小说《尤利西斯》,是敲门的意思。吉尼斯纪录的最长回文英文单词是detartrated,是个化学术语。另外,还有些已出版的英文回文小说(你们歪果仁真会玩),比如Satire: Veritas,Dr Awkward & Olson in Oslo等。

这篇关于【算法知识总结】最长回文子串-Manacher算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1025676

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

sqlite3 相关知识

WAL 模式 VS 回滚模式 特性WAL 模式回滚模式(Rollback Journal)定义使用写前日志来记录变更。使用回滚日志来记录事务的所有修改。特点更高的并发性和性能;支持多读者和单写者。支持安全的事务回滚,但并发性较低。性能写入性能更好,尤其是读多写少的场景。写操作会造成较大的性能开销,尤其是在事务开始时。写入流程数据首先写入 WAL 文件,然后才从 WAL 刷新到主数据库。数据在开始

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.