最长回文算法（马拉车算法）分析



寻找字符串中的最长回文

前几天在leetcode上做了下算法题，遇到一个非常有意思的题目，寻找最长回文，leetcode上的原题是这样的：



给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

>

示例 1：

```

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

```

示例 2：

```

输入: "cbbd"

输出: "bb"

```



很自然地会想到一种暴力解法，循环遍历每一个字符获得每一种可能的字符组合，判断是否是回文并记录最长的字符。



回文很好判断，把字符翻转一次看是否和原本的相同。



显然，这是耗时最长的一种解法，怎么把耗时降低呢？



只循环一遍是最好的，以这个想法为基础，我设计了一个指针，指针每到指一个字符，便开始以这个字符为对称轴逐个字符判断两边是否相等，记录最长的回文。



但是这有个问题，以这个字符为对称轴只能判断，aba这种形式的奇数回文，aaaa这种偶数回文没办法，所以需要在这个基础上加上以两字符中间为对称轴逐个判断两边是否相等...



合并奇偶回文处理

有没有办法把奇数和偶数回文的处理合并在一起？



做法很简单但非常巧妙，在字符之间加上一个特殊字符就可以了，



例如：

abab -> a#b#a#b

aba -> a#b#a



那么无论是奇数还是偶数都能把字符串变成奇数形式又不丢失信息。



这样做还有一个问题，假设给定字符是abb，我们首先转变为a#b#b,那么按照算法，当指针指到中间的b时，最长回文为#b#。



然后指针移到下一个字符#,这时最长回文为b#b,长度并不会比之前得到的#b#要长，所以这个回文不会成为最长回文，最后输出反而是#b#，即b。



这并不是什么大问题，只要我们在判断是否是最长回文的时候把#号去掉再判断不就好了？



没错，这是我所想到最好的解决办法了。



怎么优化?

到目前为止，这个算法比暴力解法要好很多了，面对字符串较少的情况下我满足了,对于字符串较多的优化，我默默打开了leetcode的提示，看了一下：



1. How can we reuse a previously computed palindrome to compute a larger palindrome?

2. If “aba” is a palindrome, is “xabax” and palindrome? Similarly is “xabay” a palindrome?

3. Complexity based hint:

If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.



这三个提示说的都是同一件事，怎么重用之前的计算结果，



我想到一种办法，假如给定acabacabacc字符串,在指针为对称轴逐个判断两边字符是否相等过程中，如果遇到不相等的字符，则指针直接跳到以最右边不相等的字符，再以这字符为对称轴继续逐个判断两边。



因为我想到既然对称轴两边字符都相等，那么以这两边字符为中心的回文也会一样。



我用这种想法，把代码实现了，测试了一下，发现并不能找出最长的回文。那么到底错在哪里呢？



Manacher 马拉车算法



下面开始说说这著名的马拉车算法，就是如何利用回文对称特性去减少计算量。



其实我之前想的办法已经比较接近马拉车算法的核心了，但是指针并不能简单直接跳到以最右侧不相等的字符。



继续拿acabacabacc为例子，我的算法首先会遇到acabaca这个比较长的回文，然后直接拿紧接着的b作为指针继续判断，然而最长的回文却是以第六位的c字符为对称轴的cabacabac。



因为头3位(aca)已经判断出以第2位c为轴的aca是回文，所以aca|b|aca右边的c只能重用左边aca这个结果，那么还是要继续判断b|aca|b是否是回文。



以上就是马拉车算法的基本思路了，剩下就是具体实现细节。



首先我们需要一个记录回文右边界的指针，这个用来干嘛后面再说。



然后我们需要一个记录以每个字符为回文中心的最长半径长度。



现在我们在计算中得到的信息是这样的：



计算到aca|b|aca



字符|a|c|a|b|a|c|a|b|a|c|c

-|-|-|-|-|-|-|-|-|-|-|-

序号|0|1|2|3|4|5|6|7|8|9|10

半径|0|1|0|3|0|0|0|0|0|0|0



如果两边相等，那么我们可以把表格更新为：



字符|a|c|a|b|a|c|a|b|a|c|c

-|-|-|-|-|-|-|-|-|-|-|-

序号|0|1|2|3|4|5|6|7|8|9|10

半径|0|1|0|3|0|1|0|0|0|0|0



因为回文最右侧字符序号是6，则将右边界序号设为6,



如果序号+半径大于右边界序号，就表示需要继续以那个序号往外判断。



以上边表格可以看出序号5的c为轴继续判断b|aca|b是否为回文，如果是则更新表格，更新右边界，以此类推。



其实上一节提到的abb问题，可以改变一下加#的办法，只要在a#b#b的基础上再包两个#变成#a#b#b#就可以避免问题了。为什么呢？



当处理到第二个b时最长回文是#b#，而下一个字符#的最长回文是#b#b#，恰好多一个#，可以让边界适当扩展了一下得到正确的最长回文bb。



代码实现

最后，这里给出JavaScript的实现代码，



/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  const str = '#'+s.split('').join('#')+'#';
  let len = str.length;
  // 右边界
  let rightSide = 0;
  // 右边界对应的回文串中心
  let rightSideCenter = 0;
  // 保存以每个字符为中心的回文长度一半（向下取整）
  let halfLenArr = new Array(len).fill(0);
  // 记录回文中心
  let center = 0;
  // 记录最长回文长度
  let longestHalf = 0;
  let leftCenter = 0;
  let longest = 0;
  for(let i=0; i<len; i++) {
    let needCalc = true;
    if(rightSide > i) {
      // 计算相对rightSideCenter的对称位置
      leftCenter = 2 * rightSideCenter - i;
      // 根据回文性质得到的结论
      halfLenArr[i] = halfLenArr[leftCenter];
      // 如果超过了右边界，进行调整
      if(i + halfLenArr[i] > rightSide) {
        halfLenArr[i] = rightSide - i;
      }
      // 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了
      if(i + halfLenArr[leftCenter] < rightSide) {
        // 直接推出结论
        needCalc = false;
      }
    }
    // 中心扩展
    if(needCalc) {
      while(i - 1 - halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {
        if(str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i - 1 - halfLenArr[i])) {
          halfLenArr[i]++;
        } else {
          break;
        }
      }
      // 更新右边界及中心
      rightSide = i + halfLenArr[i];
      rightSideCenter = i;
      // 记录最长回文串
      if(halfLenArr[i] > longestHalf) {
        center = i;
        longestHalf = halfLenArr[i];
        longest = halfLenArr[i];
      }
    }
  }
  return str.slice(center - longest, center + longest + 1).replace(/#/g,'');
}

文章原创于本人博客 原文链接