江苏龙网

  1. 首页 > 资讯 > 科技 > >

『IT知识课堂TB』求最长回文子串算法——马拉车算法( 二 )


结论：最长回文子串的起始索引int index = (i - p[i])/2 。
05 计算p数组
在第三步和第四步中我们都用到了一个关键对象p数组 ， 存放的是最长回文子串半径 ， 那么它是怎么来的呢？ 还是以上面的例子配合着看 ，
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
arr[i] $ # c # a # b # b # a # f # @
p[i] 1 2 1 2 1 2 5 2 1 2 1 2 1
设置两个变量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 。

『IT知识课堂TB』求最长回文子串算法——马拉车算法
本文插图

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后面的子串 ， 依旧需要去比较字符计算 。

『IT知识课堂TB』求最长回文子串算法——马拉车算法
本文插图


『IT知识课堂TB』求最长回文子串算法——马拉车算法
本文插图

06 小结
【『IT知识课堂TB』求最长回文子串算法——马拉车算法】马拉车算法将求解最长回文子串的时间复杂度降低到了O(N) ， 虽然也牺牲了部分空间 ， 其空间复杂度为O(N) ， 但是其算法的巧妙之处还是值得学习和借鉴的 。


推荐阅读


上一篇：【长旭数码】华为新机发布不断，荣耀30将搭载麒麟985处理器，颜值担当

下一篇：[蓝牙]基于BlueCore2External芯片的蓝牙主机模型方案