Manacher算法之js实现

算法 javascript, js, manacher, 算法 评论

3.Manacher算法

3.1. manacher算法

给定一个字符串，找出其最长回文子串（子串在原字符串必须连续，子序列不一定要连续）.
例如：
s=”1234”，最长回文长度为 1；
s=”12321”，最长回文长度为 5；
s=”12332”，最长回文长度为 4，即2332。
笨办法：遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为O(n^2)。
Manacher算法：时间复杂度O(n)
a) 因为存在奇回文和偶回文，所以在字符串首尾以及中间插入特殊字符。偶回文则以特殊字符为中心，便可以一起处理。
例如：12332加入特殊字符后变成#1#2#3#2#3#，中心为红色的#号。
b) 定义一个辅助数组pArr，数组的第i点的值表示以i点为中心时的最大回文半径。
例如：

str#1#2#3#3#2#
pArr12121252121

无回文时，以自己为半径，所以半径为1。可以看出pArr-1为该点的最大回文长度。
c) 之后就是计算pArr数组的方法。首先以R记录到i点之前所有回文的右边界，index为该右边界所在回文的中心点，则左边界L=index-R。计算i点为半径的最大回文半径时，分四种情况：
1） i点在R的外部，则计算以i点为中心两边的回文长度；
2） i在R的内部，且i关于index的对称点i’的回文左边界在L内部，则i的最大回文半径和i’相等。
3） i在R的内部，且i关于index的对称点i’的回文左边界在L外部，则i的最大回文半径为R-i。
4） i在R的内部，且i关于index的对称点i’的回文左边界与L相等，则i的最小回文半径为R-i，直接比较最小半径以外的数值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * 往字符串中每个字符中间插入#号
 * @param str
 * @returns {Array}
 */
function manacherString(str) {
  var arr = 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 ? '#' : arr[index++];
  }
return res;
}
/**
 * 确定字符串中最大回文长度
 * @param str
 * @returns {number}
 */
function maxLcpsLength(str) {
  if (str.length === 0) {
    return 0;
  }
  var arr = manacherString(str);  
  var pArr = new Array(arr.length); //每一点的最大回文半径
  //最右回文的中心点位置
  var index = -1;
  //所有回文的最右边界
  var R = -1;
  //最大回文半径
  var max = Number.MIN_VALUE;
  for (var i = 0; i !== arr.length; i++) {
    //确定i是否在最右回文半径中，若i在半径中，则i的半径至少是对称点半径与i点右边到最大回文半径的最小值；
    pArr[i] = R > i ? Math.min(pArr[2 * index - i], R - i) : 1;
    //确认i点回文长度未超过字符串长度，
    while (i + pArr[i] < arr.length && i - pArr[i] > -1) {
      //确定i点回文半径两边的点是否相等
      if (arr[i + pArr[i]] === arr[i - pArr[i]]) {
        //相等时i点回文半径加1，继续循环
        pArr[i]++;
      } else {
        //不相等时退出循环
        break;
      }
    }
    //修改最大回文半径时的右边界,与最大回文半径的中心点
    if (i + pArr[i] > R) {
      R = i + pArr[i];
      index = i;
    }
   max = Math.max(max, pArr[i]);
   }
return max-1;
}
console.log(maxLcpsLength('a123321bcd'));

3.2. Manacher算法扩展题目

　　给定一个字符串str1， 只能往str1的后面添加字符变成str2， 要求str2整体都是回文串且最短。
举例：str1 = ABC12321, 返回ABC12321CBA.
解法：重复manacher算法，当回文最右边界R到达str1的最后一位时，结束manacher算法，然后将str中L外部的子串逆序放在str1后面。

waldosiaWeb Developer & Designer

尾巴