国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Manacher算法

buildupchao / 1856人閱讀

摘要:若他的子串為回文串,則相對(duì)于對(duì)稱的另一端子串必然是回文串。回文串必定是中心對(duì)稱的,也就是。目前確定的是回文半徑范圍內(nèi)能確定的值,對(duì)于半徑外的字符因?yàn)椴恢苣芊窈鸵阎匚拇^續(xù)構(gòu)成更大回文串,所以也要進(jìn)行判斷。

今天思考一道題的時(shí)候,學(xué)習(xí)了一些思路,其中 Manacher 算法很有必要記錄下來(lái)。
本文參考了:http://blog.csdn.net/ggggiqny...

這道題的內(nèi)容是:

給定字符串,找到它的最長(zhǎng)回文子串

最簡(jiǎn)單的思路莫過于找到給定字符串的所有子字符串,然后一個(gè)個(gè)的判斷他們是否是回文字符串,在判斷的時(shí)候用一個(gè)變量把最長(zhǎng)的回文字符串記錄下來(lái)就可以了;
判斷是不是回文字符串很容易

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

這種簡(jiǎn)單粗暴的算法帶來(lái)的后果就是:查找子串時(shí)間復(fù)雜度O(n^2),判斷回文時(shí)間復(fù)雜度O(n),太費(fèi)時(shí)間;浪費(fèi)時(shí)間的主要原因是沒有充分地利用獲得的信息。

————————————————————分界線————————————————————————

Manacher算法非常巧妙,使用了一些輔助技巧使得整個(gè)算法的時(shí)間復(fù)雜度變?yōu)榫€性。
我們先明確兩件事:

一個(gè)字符串是回文字符串,其中間位置為m。若他的子串S[i,i+x]為回文串,則相對(duì)于m對(duì)稱的另一端子串S[2m-i, 2m-(i+x)]必然是回文串。

回文串必定是中心對(duì)稱的,也就是:S[i] == S[2m-i]。

首先,Manacher算法使用了如下的一個(gè)技巧讓我們不用考慮字符串的奇偶性問題:
每一個(gè)字符兩邊都加上一個(gè)特殊字符,比如以字符串"abba"為例,轉(zhuǎn)換后變成"#a#b#b#a#"。這樣一來(lái)字符串無(wú)論本來(lái)是奇數(shù)還是偶數(shù),都會(huì)變成奇數(shù)。

function getNewString(str){
    var newStr = "#";   
    for(i = 0;i

然后設(shè)置了一個(gè)概念:創(chuàng)建一個(gè)新數(shù)組P, P[i]項(xiàng)表示以第i個(gè)字符為中心的回文字串的半徑。比如

S  #  a  #  b  #  b  #  a  #  
P  1  2  1  2  5  2  1  2  1

通過表格可以發(fā)現(xiàn),P[i]-1就是實(shí)際回文字串的長(zhǎng)度(對(duì)應(yīng)的是符號(hào)還是數(shù)字都沒關(guān)系)。
所以我們的任務(wù)轉(zhuǎn)化為了求解數(shù)組 P;
求解數(shù)組 P 是本算法核心,根據(jù)我的理解,將其概括為如下:
設(shè)置兩個(gè)輔助參數(shù):id 和 mx;id表示當(dāng)前已記載過的邊界最大的回文字符串的中心位置,mx此回文字符串的邊界值,也就是id+p[i]
初始化一便數(shù)組P,以避免數(shù)組中有undefined:

 for(i = 0;i

接下來(lái)開始討論:
記 i 對(duì)應(yīng)于中心點(diǎn) id 的對(duì)應(yīng)位置為j,即j = 2*id - i;
若當(dāng)前已記載的最大邊境 mx > i(即 i 位置對(duì)應(yīng)的字符在已知回文字符串內(nèi)),那么:

p[i] = Math.min(p[j], mx-i);

就是當(dāng)前面比較的最遠(yuǎn)長(zhǎng)度 mx > i 的時(shí)候,P[i]有一個(gè)最小值,這就是本算法最核心的性質(zhì)。

目前確定的P[i]是回文半徑范圍內(nèi)能確定的值,對(duì)于半徑外的字符,因?yàn)椴恢苣芊窈鸵阎匚拇^續(xù)構(gòu)成更大回文串,所以也要進(jìn)行判斷。

while ((newStr[i + p[i]] == newStr[i - p[i]]) && newStr[i + p[i]]){  
            p[i]++;  
        }  

最后一步,當(dāng)有更大的回文串出現(xiàn)時(shí),更新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 = "#";       // 將字符串轉(zhuǎn)化為奇數(shù)長(zhǎng)度獲取到新的字符串 
    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]++;  
        }  
        
        // 當(dāng)有更大的回文串出現(xiàn)時(shí),更新中心位置和最大邊界值
        if (i + p[i] > mx) {  
            id = i;  
            mx = id + p[i];  
        }  
    }  
    return p;  
}  

獲得數(shù)組 p 之后,我們就獲取到P的最大值,上面的例子中,最大值是 p[4] = 5;因?yàn)榛匚陌霃剿懔俗约涸趦?nèi),所以要減去1,所以回文字符串應(yīng)該是從newStr[4-4]起,到newStr[4+4]為止。用newStr.subString(0,8)方法獲得字符串后,再去掉『#』符號(hào)就可以了;

newstr.subString(0, 8).split("#").join("");

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/86908.html

相關(guān)文章

  • 最長(zhǎng)回文子串——Manacher 算法

    摘要:?jiǎn)栴}定義最長(zhǎng)回文子串問題給定一個(gè)字符串,求它的最長(zhǎng)回文子串長(zhǎng)度。可以采用動(dòng)態(tài)規(guī)劃,列舉回文串的起點(diǎn)或者終點(diǎn)來(lái)解最長(zhǎng)回文串問題,無(wú)需討論串長(zhǎng)度的奇偶性。 0. 問題定義 最長(zhǎng)回文子串問題:給定一個(gè)字符串,求它的最長(zhǎng)回文子串長(zhǎng)度。 如果一個(gè)字符串正著讀和反著讀是一樣的,那它就是回文串。下面是一些回文串的實(shí)例: 12321 a aba abba aaaa tatt...

    mingzhong 評(píng)論0 收藏0
  • LeetCode——Longest Palindromic Substring

    摘要:題目即求最長(zhǎng)回文子序列原題鏈接此篇博客僅為學(xué)習(xí)記錄我的解法及代碼暴力解決,用及進(jìn)行兩層遍歷循環(huán)中套一層循環(huán),用遍歷,求最長(zhǎng)回文序列字符串,同時(shí)用變量記錄最長(zhǎng)子序列這種寫法很暴力,效率很低,一層循環(huán),一層循環(huán),回文序列對(duì)比一層,時(shí)間復(fù)雜度為辣 題目: Given a string s, find the longest palindromic substring in s. You ma...

    shevy 評(píng)論0 收藏0
  • [Leetcode] Longest Palindromic Substring 最長(zhǎng)回文子字符串

    摘要:這種解法中,外層循環(huán)遍歷的是子字符串的中心點(diǎn),內(nèi)層循環(huán)則是從中心擴(kuò)散,一旦不是回文就不再計(jì)算其他以此為中心的較大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...

    KnewOne 評(píng)論0 收藏0
  • 分析Longest Palindromic Substring的JS解法

    摘要:通過使用,我們將無(wú)論是奇數(shù)還是偶數(shù)的回文串,都變成了一個(gè)以為中心,為半徑兩個(gè)方向擴(kuò)展的問題。并且就是回文串的長(zhǎng)度。 Given a string s, find the longest palindromic substring in s. 這題的意思是找出 最長(zhǎng)連續(xù)回文串。 思路來(lái)源于此 這里描述了一個(gè)叫Manacher’s Algorithm的算法。 算法首先將輸入字符串S, 轉(zhuǎn)換...

    noONE 評(píng)論0 收藏0
  • 最長(zhǎng)回文子串

    摘要:給定一個(gè)字符串,找到中最長(zhǎng)的回文子串。你可以假設(shè)的最大長(zhǎng)度為。示例輸入輸出注意也是一個(gè)有效答案。 給定一個(gè)字符串 s,找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。 示例 1: 輸入: babad輸出: bab注意: aba 也是一個(gè)有效答案。 示例 2: 輸入: cbbd輸出: bb 用的Manacher算法 var longestPalindrome = fu...

    jemygraw 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<