Manacher算法如何确定数组中最大回文半径？

本文共计1667个文字，预计阅读时间需要7分钟。

在字符串`str`中，最长回文子串的长度如何求解？如何做到时间复杂度O(N)？如何直接计算字符串中每一个字符两边的节点是否对称？

例如：`str=ababa`，可以得出最大回文子串是`ababa`，长度为5。

求解方法如下：

1. 中心扩展法： - 将字符串中的每个字符和每个字符之间的空隙都看作一个可能的中心点。 - 对于每个中心点，向左右两边扩展，比较两边的字符是否相同。 - 记录下扩展过程中遇到的最大的回文子串长度。

2. 时间复杂度O(N)： - 由于每个字符最多被扩展两次（一次作为左中心，一次作为右中心），因此总的时间复杂度为O(N)。

3. 直接计算字符两边的节点是否对称： - 对于字符串中的每个字符，向左和向右扩展，比较两边的字符是否相同。 - 如果相同，则该字符两边的节点是对称的。 - 重复此过程，直到找到最大的对称节点。

示例代码（Python）：

pythondef longest_palindrome(s): if not s: return

start, end=0, 0

for i in range(len(s)): len1=expand_around_center(s, i, i) # 以字符为中心的回文子串 len2=expand_around_center(s, i, i + 1) # 以字符之间的空隙为中心的回文子串 max_len=max(len1, len2)

if max_len > end - start: start=i - (max_len - 1) // 2 end=i + max_len // 2

return s[start:end + 1]

def expand_around_center(s, left, right): while left >=0 and right

测试str=ababaprint(longest_palindrome(str)) # 输出: ababa

字符串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 }