Manacher算法计算计算数组中最长回文数半径

字符串str中,最长回文子串的长度如何求解 ?

如何做到时间复杂度O(N)完成 ?

如果直接计算字符串中每一个字符两边的节点是否对称,例: str = "ababa",可以得出最大回文子串是ababa,长度为5,有以下缺陷

• 时间复杂度较高
• 当最长回文字串的长度为偶数长度时,无法得出,例: str = "abba",由于该方法只对比每个字符两边是否对称,因此得到最长回文子串长度为0,而不是4(abba)

因此可以采用下列方法进行求解

将字符串转化成数组,并在每两个字符中间插入'#',如下

str = "abba",转化后为arr = ['#','a','#','b','#','b','#','a']

计算每个节点处的回文半径r,最后r-1的结果就是最长的回文字串长度(除去中间插入#的长度)

当当前遍历的节点i在前面结束位置最长的回文子串半径中,直接与其在回文子串中的对称点i'进行比较

• 如果i'的回文子串长度仍在最长的回文子串长度内,则i的回文子串应该也在该回文子串内

  

   

• 如果i'的回文子串长度已经超过i'到最长的回文子串长度边的距离,先将i的回文字串半径赋值为最长的回文子串长度减去i的下标,在这段距离内,i两边是回文的,超出最长的回文子串长度后的数据需要另行判断

• 如果i'的回文子串长度刚好等于i'到最长的回文子串长度边的距离,先将i的回文字串半径赋值为最长的回文子串长度减去i的下标,在这段距离内,i两边是回文的,超出最长的回文子串长度后的数据需要另行判断

代码:

 1 /**
 2  * manacherString函数
 3  * 将字符串转化成Manacher形式
 4  * 1221 -> #1#2#2#3#
 5  */
 6 const manacherString = (str) => {
 7     let charArr = str.split(''); // 转化成数组
 8     let res = new Array(str.length * 2 + 1); // 用于存储转化后的数组
 9     let index = 0;
10     for(let i = 0;i < res.length;i++){
11         /**
12          * 计算,当i与1进行与运算后等于0,插入'#'(偶数位)
13          * 0 & 1 = 0 (00000000 & 00000001 = 0)
14          * 1 & 1 = 1 (00000001 & 00000001 = 1)
15          * 2 & 1 = 0 (00000010 & 00000001 = 0)
16          * 3 & 1 = 1 (00000011 & 00000001 = 1)
17          * ......
18          */
19         res[i] = [i & 1] == 0 ? '#' : charArr[index++];
20     }
21     // 返回转化后的字符数组
22     return res;
23 }
24 
25 // 计算最长回文子串的长度
26 const maxLcpLength = (s) => {
27     // 如果字符串不存在或者为空串,最长回文子串的长度为0
28     if(!s || s.length == 0) return 0;
29     // 1221 -> ['#','1','#','2','#','2','#','1','#']
30     let str = manacherString(s); // 将字符串s转化成字符数组str
31     let pArr = new Array(str.length); // 记录每个节点处的回文半径的数组
32     let C = -1; // 记录对称中心
33     let R = -1; // 记录回文半径
34     let max = -Number.MAX_VALUE; // 记录扩出来的最大值'
35     for(let i = 0;i < str.length;i++){
36         // 求每个位置的回文半径
37         // 先计算出i最少回文的半径,赋值给pArr[i]
38         if(R > i){
39             // 如果i在R范围内(最右回文长度)
40             /**
41              * 在回文半径内时
42              * 比较与i对称的i'的pArr长度和R-i长度
43              * 1. 如果i'的pArr长度在R内,pArr[i] = pArr[i']
44              * 2. 如果i'的pArr长度已经超过i'到R边的距离,先将pArr[i]赋值为R-i,在这段距离内,i两边是回文的,超出R后的数据需要另行判断
45              * 3. 如果二者相等,赋值给pArr[i],再比较外面是否也符合回文条件
46              */
47             pArr[i] = Math.min(pArr[2*C-i],R-i);
48         }
49         else pArr[i] = 1; // 自己回文对称(前后再进行判断,先将回文长度赋值最小值1)
50         while(i+pArr[i] < str.length && i-pArr[i] > -1){
51             // 当还在数组内部的时候
52             // 当左扩和右扩一位的值相同的时候,回文数半径+1
53             if(str[i+pArr[i]] === str[i-pArr[i]]) pArr[i]++;
54             else break; // 左扩右扩 不相等,停止循环,寻找下一个节点的回文半径
55         }
56         // R记录最大的右扩长度
57         // C记录右扩最大的对称中心
58         if(i + pArr[i] > R) {
59             R = i + pArr[i];
60             C = i;
61         }
62         // 记录最长的回文数长度
63         max = Math.max(max,pArr[i]);
64     }
65     // 半径-1就是原串最大的回文长度
66     return max-1;
67 }