JavaScript Manacher 算法

Manacher 算法

当一段字符串正序倒序都一样的成为回文：12321 就是回文字符串

manacherString

a12321b 回文的长度为 5，奇数，回文中点位置是 3。
a1221b 回文长度为 4，偶数，回文中点位置确定不了。
为了解决偶数回文确定中点的位置可以将字符串生成为一段特殊符号填充字符串
#a#1#2#2#1#b# 回文中点位置是 6，长度是 #1#2#2#1# 字符串长度 9 % 2 = 4

function manacherString(str) {
  var strArr = str.split('')
  var res = new Array(str.length * 2 + 1)
  var index = 0
  for (var i = 0; i !== res.length; i++) {
    res[i] = (i & 1) === 0 ? '#' : strArr[index++]
  }
  return res
}

求解最大回文长度

解法思路

首先确定一个回文字符串，标记左右位置是 L 和 R
找到中心点 C

在遍历时 i 位置都会在中心点对称位置有一个 i' 的对称点
一直记录这个 i 点的当前回文直径。
直到找到最大一段回文的长度

解法过程中的多个情况

在遍历字符串求解最大回文直径的时会有两种分支四种情况

i >= R 分支一, i 超过 R 点，i' 超过 L

i 位置的回文直径只有他自己为1, R 扩大

C < i < R 分支二， 情况1 i' 的回文长度不超过 L

此情况下，i' 边界 在 L 内 不扩大

因为 L - R 本身为回文， 这时候 i' 到 L 的位置无需继续考察

C < i < R 分支二， 情况1 i' 的回文长度在 L - i' 之中

此情况下，i' 边界 超过 L 不扩大

因为 L - R 本身为回文，i' 位置回文长度超过 L 但是回文边界是无法超过 L 的，无需向外考察和扩大

C < i < R 分支二， 情况1 i' 的回文长度刚好压在 L 位置

此情况下，L 位置与 i' 边界重合，i 回文边界在 R 内 需要继续考察下一位 R 扩大

向外扩大条件

当 i 位置回文长度被推的比 R 远时，要记录 R 和 C 的新位置, 新 R 为 i 推向的位置，C 为 i 当下位置

代码

function maxLcpsLength(str) {
  if (str === null || str.length === 0) return 0
  
  var strArr = manacherString(str)
  var pArr = new Array(strArr.length) // 用来描述字符串每个位置的回文长度信息
  var C = -1
  var R = -1 // 右边界
  var max = Number.MIN_SAFE_INTEGER
  for (var i = 0; i !== strArr.length; i++) {
    // 告知 i 位置的回文半径起码是多远, i 位置不用验的区域
    pArr[i] = R > i/*分支二情况*/ 
      ? Math.min(pArr[2 * C - i], R - i)/*i'对称点，整合情况1，2 不用验的区域*/ 
      : 1/*分支一情况, 回文半径为1*/
    // 在得知最基础的 i 位置的回文半径下尝试 R 是否可外扩
    while (i + pArr[i]/*左边界*/ < strArr.length && i - pArr[i]/*右边界*/ > -1) { // 判断是否越界
      if (strArr[i + pArr[i]] === strArr[i - pArr[i]])
        pArr[i]++ // 没越界且相等，回文边界增加
      else
        break // 分支一，分支二情况4，不可外扩直接 break
    }
    if (i + pArr[i] > R) { // 如果回文右边界推的更远了，就记录新的 R C
      R = i + pArr[i]
      C = i
    }
    max = Math.max(max, pArr[i])
  }  
  return max - 1
}