Manacher算法

buildupchao 發布于2019-08-21 11:36 / 1872人閱讀

摘要：若他的子串為回文串，則相對于對稱的另一端子串必然是回文串。回文串必定是中心對稱的，也就是。目前確定的是回文半徑范圍內能確定的值，對于半徑外的字符因為不知能能否和已知回文串繼續構成更大回文串，所以也要進行判斷。

今天思考一道題的時候，學習了一些思路，其中 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 數據結構算法算法字符串處理算法匹配算法爬山算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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