动态规划之马拉车算法

Kubrnete
• 阅读 1589

问题描述:

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。如"abc"有三个回文子串‘a','b','c'.

示例 1:

输入:"abc" 输出:3 解释:三个回文子串: "a", "b", "c"

示例 2:

输入:"aaa" 输出:6 解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

对于这个问题,简单的思路是枚举字符串中的每个子串,然后判断子串中回文串的个数。O(N^3)

本篇文章主要介绍我个人对马拉车算法实现思路的一些想法,原题解请看leetcode-647.回文子串


中心拓展法

由于回文串有对称性这一特点,每个回文串必然存在一个对称中心。我们可以对字符串中每个字符或两个字符之间的位置(若回文串长度为偶数)当作对称中心进行枚举,例如s="abcba",当i=2时,判断a[1]==a[3],a[0]==a[4].....如果左右两边字符相同时则继续扩展,一旦不相同则更新最大扩展长度并退出当前循环,继续枚举下一个对称中心。

假设字符串的长度为 n,枚举每个对称中心(长度为 1 和 0的对称中心分别有 n 和 n-1 个),共遍历2n-1次,时间复杂度为 O(n);每个对称中心最多向外拓展n次,所以整体的时间复杂度是 O(n^2)。空间复杂度为O(1)。

代码如下(直接抄leetcode了):

//遍历2n-1次,就能够得到所有可能的对称中心
for (int i = 0; i < 2 * n - 1; i++) {
            int l = i / 2, r = i / 2 + i % 2;//这样能够把长度为奇数和偶数的两种情况统一起来。
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
                ++ans;
            }
        }

动态规划之马拉车算法

还有没有优化的空间呢?让我们看看在中心拓展法中出现的两个问题,然后了解一下马拉车算法如何对这两个问题进行处理。

1. 长回文串中的重复查找(关键):

为了更简单直接地说明问题,我举一个极端的特例:字符串s="aaaaaaa",并先对奇回文子串进行查找。尽管我们在以第2位字符为对称中心左右扩展时能够发现左回文子串s1="aaa",并且以第四位字符为对称中心左右扩展能够发现了长回文串s,那么之后的查找中是否仍需要匹配后三位字符串呢?设Im为长回文串的对称中心

动态规划之马拉车算法

动态规划之马拉车算法

其实,我们可以发现,若在一个长回文串中发现了左回文子串,根据回文串的对称性,那么在一定区域内的右子串中必然也存在一个回文串。因此,上述重复查找过程是可以省去的。

2.对长度奇数或偶数的回文子串分情况讨论

马拉车算法:

一、算法分析:

马拉车算法的核心思路就在于,对每个长回文串的对称中心向两边进行拓展,同时记下前面已经查找过的回文子串半径(原理是动态规划的思想),其本质在于,如果能够找到一个长回文串,同时在它的对称中心左区域中找到一个回文子串,由于回文串的对称性,其右区域中必然是同样的回文子串。因此这个算法能快速地找出最长的回文子串。当然也能用来求解回文子串的个数。

二、算法实现:

1.预处理(解决了奇偶回文串问题):

  • 为了利用回文串的对称性,同时解决回文子串长度有奇数和偶数两种情况的问题,马拉车算法在字符串首尾及每个字符间都插入一个 "#"。可以发现,无论回文子串原来是奇数还是偶数,最终都会变成奇回文子串,因此能够统一处理。即令原字符串为s,预处理后有 ts = s.replace('', '#')

  • 我们定义①

    当前向两边拓展距离最大的回文串为最大回文串,即一个长回文串;②

    从对称中心到左端点的距离为最大回文半径,并假设为d;

    当我们求出最大回文半径d时,

    最大回文串

    的长度正好是d。

    动态规划之马拉车算法

    动态规划之马拉车算法

  • 另外,在下面的步骤中,为了避免数组越界,我们还要在字符串开头加一个"$",结尾加一个"!",这样开头和结尾的两个字符一定不相等,循环就可以在这里终止。

预处理代码如下

s = '$' + input().replace('', '#') + '!'
#为了避免数组越界,让开头和结尾的两个字符一定不相等,循环就可以在这里终止。

动态规划之马拉车算法

2.初始化(解决了重复查找问题):

  • 数据结构与逻辑变量:马拉车算法的要求维护的变量有,一个数组d[]记录最大回文半径,d[i]表示以第i位元素为对称中心的最大回文半径,初始化长度为0(半径算上中心就是1);当前最大回文串的(即长回文串)对称中心Im及其右端点r,初始化皆为0。
  • 初始化
  • 以字符串"dadbdac"为例

动态规划之马拉车算法

动态规划之马拉车算法

这里有两种情况:

  • Case 1: i<=r,即当前枚举的对称中心i被包含在当前最大回文串内,此时拓展过程可以加速
  1. 当找到一个长回文串时,取其对称中心为Im,对于其中的每个对称中心i,我们可以求出关于Im的对称位置 j=2*Im-i
  2. 在这个长回文串范围内,可以通过对称性得到d[i]=d[j] 。
  3. 注意当d[j]>r-i时,通过d加速拓展的右子串超出了长回文串的范围。然而大于右端点的回文串我们还没有开始匹配,此时d[i] = r - i . 比方说,当Im=3时,有r=5;当i=5时,有j=1,并且前面已经算出d[j] = 1。此时d[j]>r-i,向右拓展超出了长回文串范围,则d[i]应为i到右端点r的距离,即r-i。因此,当对称中心i被包含在当前最大回文串内时,有

d[i]=min(d[2 * Im - i],r - i) (核心:如果d[j]+i<=r,则d[i]=d[j],否则d[i]=r-i)

  • Case 2 : i>r\,此时用常规的中心拓展法更新d[]、Im以及r。

3.中心拓展

经过了上面的初始化,我们每次枚举对称中心的时候就都能够保证 s[i-d[i]]=s[i+d[i]],而现在,只要再满足ts[i - d[i]-1]==ts[i + d[i]+1],则不断向左右两边拓展半径。

综上所述,我们能够写出马拉车算法的核心代码:

for i in range(2, len(s)-2):      
    if(i<=r):#当对称中心i被包含在当前最大回文串内时,拓展过程可以加速(核心)
        d[i]=min(d[2 * Im - i] , r - i )
    while (s[i - d[i] - 1] == s[i + d[i] + 1]):#满足条件,向左右拓展半径
        d[i] += 1

动态规划之马拉车算法

4.维护当前最大回文串的对称中心Im和r

我们仍以字符串"dadbdac"为例,求d时可以只看s[2:len-2):

s $ # d # a # d # b # d # a # c # !
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
d[i] 1 0 3 0 1 0 5 0 1 0 1 0 1

其实在上述的核心思路中,在枚举每个回文子串的对称中心时,也在不断匹配最大回文串并更新Im和r。利用已经算出来的状态来更新d[i],这就是一种动态规划的思想

对于一个回文串,我们用d[i]记录了其对称中心到右端点的距离。以上面的例子来说明,当i=8时(属于i>r的情况),计算出d[i]=5,则此时容易得到r=i+d[i]=13,同时更新Im=8。对于i<=r的情况,如果i+d[i]>r,说明当前对称中心i拓展出了回文串,于是此时需要更新对称中心Im为i,右端点r为i+d[i]。而对于i>r的情况,由于d[i]总是等于0,此时更新Im=i,r=i

if (i + d[i] > r):
    Im, r = i, i + d[i]

动态规划之马拉车算法

顺带提一句,最开始我以为马拉车这个算法名字应该是根据Manacher英译而来,但是这个中心扩展的思路,加上通过d[i]记录了最大回文串的半径避免了重复匹配,光看这两行代码:

while (s[i - d[i] - 1] == s[i + d[i] + 1]) d[i]++;
if (i + d[i] > r){Im=i, r = i + d[i];}

动态规划之马拉车算法

真是有两头马在拉着一个对称中心向两边跑的感觉,大概就像这样:动态规划之马拉车算法)动态规划之马拉车算法

然后不断更新最大回文串的对称中心Im和 r,通过***d[i] = min(d[2 \ Im - i], r - i)快速求解**

如何求解ans就不解释啦,直接上代码:

s = '$' + input().replace('', '#') + '!'
d,Im,r,ans= [0]*(len(s)-2),0,0,0
for i in range(1, len(s)-2):    
    if (i <= r):#当对称中心i被包含在当前最大回文串内时,拓展过程可以加速
        d[i] = min(d[2 * Im - i], r - i) #核心:如果d[j]+i<=r,则d[i]=d[j],否则d[i]=r-i
    while (s[i - d[i] - 1] == s[i + d[i] + 1]):#满足条件,向左右拓展半径
        d[i] += 1
    if (i + d[i] > r):
        Im, r = i, i + d[i]
    ans += (d[i] + 1) // 2
print(ans)

动态规划之马拉车算法

这个算法总时间复杂度是O(n),空间复杂度O(n)。

另外,如果再用一个变量ma记录d[i]的最大值,稍微改一下最后两行,就可以找出字符串中的最长回文子串:

ma,ans = (d[i],ts[i-d[i]:i+d[i]]) if (d[i]>ma) else (ma,ans)
print(ans.replace('#',''))

本文转自 https://blog.csdn.net/guanguandaren/article/details/108105363,如有侵权,请联系删除。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
一只编程熊 一只编程熊
3年前
【LeetCode每日一题 Day 5】5. 最长回文子串
大家好,我是编程熊,今天是LeetCode每日一题的第五天,一起学习LeetCode第五题《最长回文子串》。题意给你一个字符串s,找到s中最长的回文子串。示例txt输入:s"babad"输出:"bab"解释:"aba"同样是符合题意的答案。题解方法一采用简单暴力的方法,枚举每一个位置为单独回文中心(长度为奇数的子串,如aba)或者回文中心
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
Stella981 Stella981
3年前
Python 学生管理
原文链接: Python学生管理(https://my.oschina.net/ahaoboy/blog/1526102)python3练手 codingutf8学生类classStu:三个字段id字符串,name字符串,score小数def__init__(sel
Stella981 Stella981
3年前
JS 苹果手机日期显示NaN问题
问题描述newDate("2019122910:30:00")在IOS下显示为NaN原因分析带的日期IOS下存在兼容问题解决方法字符串替换letdateStr"2019122910:30:00";datedateStr.repl
Wesley13 Wesley13
3年前
125. 验证回文串
\TOC\题目给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。说明:本题中,我们将空字符串定义为有效的回文串。示例1:输入:"Aman,aplan,acanal:Panama"输出:true示例2:输入:"raceacar"输出
Stella981 Stella981
3年前
JavaScript常用函数
1\.字符串长度截取functioncutstr(str,len){vartemp,icount0,patrn/^\x00\xff/,strre"";for(vari
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Stella981 Stella981
3年前
LeetCode459. 重复的子字符串
1.问题描述给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。示例1:输入:“abab”输出:True解释:可由子字符串“ab”重复两次构成。示例2:输入:“aba”输出:Fal
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这