最大回文子串之Manacher算法

概述

这道题目目前我还没有遇到应用场景，不过会解题总是不会有错的。

题目描述

对于给定的字符串s，找到其中的最大回文子串，你可以假定s的最大长度是1000。

示例1：

1
2
3

Input: "babad"
Output: "bab"
Note: "aba"也是正确答案

示例2

1 2	Input: "cbbd" Output: "bb"

暴力算法

最直观的思路，我们可以对每个点进行遍历，计算以该点为起点的最大回文子串，并和当前求得的最大回文子串进行对比，如果更大则将其记录下来。

const isPalindrome = function(s, from = 0, to = s.length) {
  const mid = ~~((from + to) / 2);
  for (let i = from; i <= mid; i++) {
    if (s[i] !== s[from + to - i - 1]) {
      return false;
    }
  }
  return true;
};

const longestPalindrome = function(s) {
  if (!s.length) {
    return '';
  }
  let bestFrom = 0;
  let bestTo = 1;
  for (let i = 0, l = s.length; i < l; i++) {
    for (let j = i + 1; j <= l; j++) {
      // 如果当前起始点的后续所有子串都比当前最佳子串还短
      // 则没有必要计算后续子串
      if (l - j > bestTo - bestFrom) {
        break;
      }
      // 如果当前子串比当前最佳子串还短
      // 则没有必要计算其是否是回文串
      if (j - i < bestTo - bestFrom) {
        j = i + bestTo - bestFrom;
      }
      if (isPalindrome(s, i, j)) {
        bestFrom = i;
        bestTo = j;
      }
    }
  }
  return s.substring(bestFrom, bestTo);
};

这种算法理解简单，实现容易，但缺点也很明显，其耗时太大，时间复杂度是$O(n^2)$。

1	longestPalindrome('abcba'); // 输出"abcba"

同学们可能注意到，我们现在的方式是遍历每一个下标所指的字符，并计算以之为起点的子串，这种做法的缺点在于，对于当前字符，在二次遍历到当前趟所剩的子串长度的一半之前，我们没有办法确定以当前字符为起点的最长回文子串。

我们可以换一种思路，如果是以当前字符为对称点，然后左右同时遍历，只要出现两边不同的情况，或者任意一边到了母串的边界，即可得到以当前字符为对称点的最大回文串。

虽然理论上来说它的时间复杂度还是$O(n^2)$，但这种改动可以有效减少二层遍历中的趟数。

const longestPalindrome = function(s) {
  if (!s.length) {
    return '';
  }
  let bestAxis = 0;
  let bestR = 0;
  for (let i = 0, l = s.length; i < l; i++) {
    // 如果以当前点为中心点的子串最大半径都不可能超过当前最佳子串半径
    // 则没有必要再处理以当前点为中心点的子串
    if ((l - i > i ? i : l - i) < bestR) {
      break;
    }
    for (let r = 0; i + r < l && i - r < l; r++) {
      if (s[i - r] !== s[i + r]) {
        break;
      }
      if (r > bestR) {
        bestR = r;
        bestAxis = i;
      }
    }
  }
  return s.substring(bestAxis - bestR, bestAxis + bestR + 1);
};

上面的改动看似可以比之前的解法更高效，但实际上却是一种错误解法。

1 2	longestPalindrome('abcba'); // 输出"abcba" longestPalindrome('abccba'); // 输出"a"，错误答案

假定我们输出的母串是abccba，我们期待的结果是abccba，但是上面的解法求得的结果却是a，这是因为我们现在要求最大回文子串必须要有一个对称点，而abccba这个解中却不存在对称点，为了满足这个要求，我们需要对abccba进行一个变形，我们在开头加上一个$号，在最尾加上一个#号，然后在每个字符之间都加入一个#号。

变形后的结果为$a#b#c#c#b#a#，现在再应用上述算法就能求得最后答案了。

const longestPalindrome = function(s) {
  if (!s.length) {
    return '';
  }
  const s2 = `$#${s.split('').join('#')}#`;
  let bestAxis = 0;
  let bestR = 0;
  for (let i = 2, l = s2.length; i < l; i++) {
    // 如果以当前点为中心点的子串最大半径都不可能超过当前最佳子串半径
    // 则没有必要再处理以当前点为中心点的子串
    if ((l - i > i ? i : l - i) < bestR) {
      break;
    }
    for (let r = 0; i + r < l && i - r < l; r++) {
      if (s2[i - r] !== s2[i + r]) {
        break;
      }
      if (r > bestR) {
        bestR = r;
        bestAxis = i;
      }
    }
  }
  return s2.substring(bestAxis - bestR, bestAxis + bestR + 1).replace(/#/g, '');;
};

Manacher算法

算法描述

接下来我们要介绍一种更高效的算法——Manacher算法，Manacher算法（Manacher’s Algorithm）是Manacher在1975年发现的一种解题算法，在此之前的解题方法的时间复杂度都是$O(n^2)$。

还是以上面的解法为基础，我们来分析一下每一个回文子串的对称规律。

TBD // 此处应有图，回头补上

算法实现

以下是JavaScript的算法实现。

const longestPalindrome = s => {
  if (!s.length) {
    return '';
  }
  const s2 = `$#${s.split('').join('#')}#`;
  const l = [];
  let i = 0;
  let axis = 0;
  let mostRight = -1;
  let maxLength = -1;
  let maxStr = s[0];
  while (i < s2.length) {
    if (i < mostRight) {
      l[i] = Math.min(l[2 * axis - i], mostRight - i);
    } else {
      l[i] = 1;
    }
    let dist = l[i];
    while (s2[i - dist] === s2[i + dist]) {
      l[i]++;
      dist++;
    }
    maxLength = Math.max(maxLength, l[i]);
    if(maxLength * 2 - 1 > maxStr.length) {
      maxStr = s2.slice(i - maxLength + 1, i + maxLength);
    }
    if (mostRight < i + l[i]) {
      axis = i;
      mostRight = i + l[i];
    }
    i++;
  }
  return maxStr.replace(/#/g, '');
};

总结

目前还没有看到这个算法有什么实用场景。