IT知识课堂TB▲求最长回文子串算法——马拉车算法( 二 )
05计算p数组
在第三步和第四步中我们都用到了一个关键对象p数组 ， 存放的是最长回文子串半径 ， 那么它是怎么来的呢？还是以上面的例子配合着看 ，
i01234567891011121314
arr[i]$#c#a#b#b#a#f#@
p[i]1212125212121
设置两个变量id和mx ， id是所有回文子串中 ， 能延伸到最右端位置的那个回文子串的中心点位置 ， mx是该回文串能延伸到的最右端的位置 。
当i等于7时 ， id等于7 ， p[id]=5 ， 在以位置7为中心的回文子串中 ， 该回文子串的右边界是位置12 。
当i等于12时 ， id等于12 ， p[id]=2 ， 在以位置12为中心的回文子串中 ， 该回文子串的右边界是位置14 。
由此我们可以得出回文子串右边界和其半径之间的关系：mx=p[id]+id 。
文章图片
image
因为回文字符串是中心对称的 ， 知道中心点位置id ， 如果一个位置的回文子串以i为中心 ， 并且包含在以id为中心的回文子串中 ， 即mx>i ， 那么肯定会存在另外一个以j为中心回文子串 ， 和以i为中心的回文子串相等且对称 ， 即p[j]=p[i] ， 而i和j是以id为中心对称 ， 即i+j=2*id ， 如果知道了i的值 ， 那么j=2*id-i 。
但是我们需要考虑另外一种情况 ， 如果存在一个以i为中心的回文子串 ， 依旧有mx>i ， 但是以i为中心的回文子串右边界超过了mx ， 在i到mx的这段回文子串中 ， 与另一端对称的以j为中心的回文子串还是相等的 ， 此时p[i]=mx-i ， p[j]=[pi] ， 至于右边界mx之外的子串 ， 即以i为中心的回文子串超出的部分是否还是满足上述条件就需要遍历比较字符了 。
因此 ， 在mx>i的情况下 ， p[i]=Math.min(p[2*id-i],mx-i) 。 另外如果i大于mx了 ， 也即是边界mx后面的子串 ， 依旧需要去比较字符计算 。
文章图片
文章图片
06小结
马拉车算法将求解最长回文子串的时间复杂度降低到了O(N) ， 虽然也牺牲了部分空间 ， 其空间复杂度为O(N) ， 但是其算法的巧妙之处还是值得学习和借鉴的 。
推荐阅读
- 美肤瘦身知识有人得到还款红包50，有人直接提额18000！，支付宝借呗服务升级
- 美肤瘦身知识很久转过几次帐，微粒贷就自动开通了82000！，小伙微信发发红包
- [科学家]全球最长水下洞穴：长600公里深百米，已发现两具玛雅人遗骸
- 「大象」虽然看起来像是假的 但却是真实情况的11个冷知识
- 风月无关地震科学专业知识服务系统介绍
- 科学家▲《我们的脑子够用吗》：与剑桥脑科学家一起探索稀奇古怪的脑知识
- #恒星#一百个宇宙冷知识 看完才明白 人类是多么渺小（第二期）
- 「数据线」手机充电速度取决于充电头还是数据线，网友：涨知识了
- 生煎娘舅木工刀具设计知识：螺纹套筒调节的组合木工铣刀结构
- 玩机课堂来看看！，微信一个隐藏彩蛋功能