Manacher算法

buildupchao 发布于2019-08-21 11:36 / 1828人阅读

摘要：若他的子串为回文串，则相对于对称的另一端子串必然是回文串。回文串必定是中心对称的，也就是。目前确定的是回文半径范围内能确定的值，对于半径外的字符因为不知能能否和已知回文串继续构成更大回文串，所以也要进行判断。

今天思考一道题的时候，学习了一些思路，其中 Manacher 算法很有必要记录下来。
本文参考了：http://blog.csdn.net/ggggiqny...

这道题的内容是：

给定字符串，找到它的最长回文子串

最简单的思路莫过于找到给定字符串的所有子字符串，然后一个个的判断他们是否是回文字符串，在判断的时候用一个变量把最长的回文字符串记录下来就可以了；
判断是不是回文字符串很容易

function isPalindrome(str) {
var newStr = str.split("").reverse().join("");
return newStr === str ? true : false;
}

获得所有子串也很容易

function getSubstring(str){
    var len = str.length;
    for(var i=0; i
这种简单粗暴的算法带来的后果就是：查找子串时间复杂度O(n^2),判断回文时间复杂度O(n)，太费时间；浪费时间的主要原因是没有充分地利用获得的信息。
————————————————————分界线————————————————————————
Manacher算法非常巧妙，使用了一些辅助技巧使得整个算法的时间复杂度变为线性。
我们先明确两件事：

一个字符串是回文字符串，其中间位置为m。若他的子串S[i,i+x]为回文串，则相对于m对称的另一端子串S[2m-i, 2m-(i+x)]必然是回文串。

回文串必定是中心对称的，也就是：S[i] == S[2m-i]。


首先，Manacher算法使用了如下的一个技巧让我们不用考虑字符串的奇偶性问题：
每一个字符两边都加上一个特殊字符,比如以字符串"abba"为例，转换后变成"#a#b#b#a#"。这样一来字符串无论本来是奇数还是偶数，都会变成奇数。
function getNewString(str){
    var newStr = "#";   
    for(i = 0;i
然后设置了一个概念：创建一个新数组P, P[i]项表示以第i个字符为中心的回文字串的半径。比如
S  #  a  #  b  #  b  #  a  #  
P  1  2  1  2  5  2  1  2  1
通过表格可以发现，P[i]-1就是实际回文字串的长度（对应的是符号还是数字都没关系）。
所以我们的任务转化为了求解数组 P；
求解数组 P 是本算法核心，根据我的理解，将其概括为如下：
设置两个辅助参数：id 和 mx；id表示当前已记载过的边界最大的回文字符串的中心位置，mx此回文字符串的边界值，也就是id+p[i]；
初始化一便数组P，以避免数组中有undefined:
 for(i = 0;i
接下来开始讨论:
记 i 对应于中心点 id 的对应位置为j，即j = 2*id - i;
若当前已记载的最大边境 mx > i(即 i 位置对应的字符在已知回文字符串内)，那么:
p[i] = Math.min(p[j], mx-i);
就是当前面比较的最远长度 mx > i 的时候，P［i］有一个最小值，这就是本算法最核心的性质。
目前确定的P[i]是回文半径范围内能确定的值，对于半径外的字符,因为不知能能否和已知回文串继续构成更大回文串，所以也要进行判断。
while ((newStr[i + p[i]] == newStr[i - p[i]]) && newStr[i + p[i]]){  
            p[i]++;  
        }  
最后一步，当有更大的回文串出现时，更新mx 和 id 的值
if (i + p[i] > mx) {  
            id = i;  
            mx = id + p[i];  
        }  
整体代码
function getArrayP(str){  
    var p = [],   
        mx = 0,  
        id = 0;  
    var i;  
     
    var newStr = "#";       // 将字符串转化为奇数长度获取到新的字符串 
    var len = str.length;  
    for(i = 0;i i ? Math.min(p[2*id-i], mx-i) : 1;   
    
        while ((newStr[i + p[i]] == newStr[i - p[i]]) && newStr[i + p[i]]){           // 超出其半径的位置再做额外判断，确保 newStr[i + p[i]] 是存在的  
            p[i]++;  
        }  
        
        // 当有更大的回文串出现时，更新中心位置和最大边界值
        if (i + p[i] > mx) {  
            id = i;  
            mx = id + p[i];  
        }  
    }  
    return p;  
}  
获得数组 p 之后，我们就获取到P的最大值，上面的例子中，最大值是 p[4] = 5;因为回文半径算了自己在内，所以要减去1,所以回文字符串应该是从newStr[4-4]起，到newStr[4+4]为止。用newStr.subString(0，8)方法获得字符串后，再去掉『#』符号就可以了；
newstr.subString(0, 8).split("#").join("");

GPU云服务器云服务器 Manacher 数据结构算法算法字符串处理算法匹配算法爬山算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/86908.html

最长回文子串——Manacher 算法

摘要：问题定义最长回文子串问题给定一个字符串，求它的最长回文子串长度。可以采用动态规划，列举回文串的起点或者终点来解最长回文串问题，无需讨论串长度的奇偶性。 0. 问题定义最长回文子串问题：给定一个字符串，求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的，那它就是回文串。下面是一些回文串的实例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 评论0 收藏0
LeetCode——Longest Palindromic Substring

摘要：题目即求最长回文子序列原题链接此篇博客仅为学习记录我的解法及代码暴力解决，用及进行两层遍历循环中套一层循环，用遍历，求最长回文序列字符串，同时用变量记录最长子序列这种写法很暴力，效率很低，一层循环，一层循环，回文序列对比一层，时间复杂度为辣题目： Given a string s, find the longest palindromic substring in s. You ma...

shevy 2019-08-23 18:26 评论0 收藏0
[Leetcode] Longest Palindromic Substring 最长回文子字符串

摘要：这种解法中，外层循环遍历的是子字符串的中心点，内层循环则是从中心扩散，一旦不是回文就不再计算其他以此为中心的较大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...

KnewOne 2019-08-14 12:17 评论0 收藏0
分析Longest Palindromic Substring的JS解法

摘要：通过使用，我们将无论是奇数还是偶数的回文串，都变成了一个以为中心，为半径两个方向扩展的问题。并且就是回文串的长度。 Given a string s, find the longest palindromic substring in s. 这题的意思是找出最长连续回文串。思路来源于此这里描述了一个叫Manacher’s Algorithm的算法。算法首先将输入字符串S，转换...

noONE 2019-08-21 11:55 评论0 收藏0
最长回文子串

摘要：给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: babad输出: bab注意: aba 也是一个有效答案。示例 2：输入: cbbd输出: bb 用的Manacher算法 var longestPalindrome = fu...

jemygraw 2019-08-23 14:44 评论0 收藏0