Manacher算法是一種用于找出給定字符串中最長(zhǎng)的回文字符子串的算法.該算法的神來(lái)之筆是: 用一個(gè)不會(huì)出現(xiàn)在該目標(biāo)字符串中的特殊字符對(duì)目標(biāo)字符串進(jìn)行填充, 為描述簡(jiǎn)便, 我們就假設(shè)該特殊符號(hào)為"#", 并且算法是從字符串的左端向右端開(kāi)始尋找.

我們這樣來(lái)完成填充:

1)在目標(biāo)字符串的每個(gè)字符前面都塞入一個(gè)"#";

2)在目標(biāo)字符串的末端加一個(gè)"#".

如此一來(lái), 任意字符串"***"填充之后都會(huì)變成這個(gè)樣子"#*#*#*#"

從填充的兩個(gè)步驟可以看出, 任意長(zhǎng)度為n的字符串, 在填充之后長(zhǎng)度都會(huì)變成n+n+1, 即2n+1, 也就是說(shuō)填充之后得到的字符串的長(zhǎng)度一定是奇數(shù).

由于后面不可避免地要討論字符的位置下標(biāo), 所以從這里開(kāi)始, 我們就把被填充后的字符串看做一個(gè)字符數(shù)組, 如果被填充前的目標(biāo)字符串長(zhǎng)度為n, 那么該字符數(shù)組的下標(biāo)顯然就是從0開(kāi)始, 到2n結(jié)束. 同時(shí)為了后續(xù)描述的統(tǒng)一和便于理解, 我們?cè)谶@個(gè)字符數(shù)組的基礎(chǔ)上定義幾個(gè)代名詞:

當(dāng)前有效回文字符串: 它是指當(dāng)前已經(jīng)找到的, 擁有最大右端下標(biāo)的回文字符串, 注意, 它不一定是已經(jīng)找到的最長(zhǎng)回文字符串.

mPoint: middle point, 它是指當(dāng)前有效回文字符串的中點(diǎn)字符的下標(biāo). mPoint的初始值是0, 它會(huì)逐漸右移.

radius: 回文字符串半徑, 由于回文字符串是關(guān)于中點(diǎn)位置對(duì)稱(chēng)的, 所以把長(zhǎng)度為n的回文字符串的半徑定義為從中點(diǎn)位置分割后, 任意一側(cè)的字符串長(zhǎng)度+1(要把中點(diǎn)位置的字符算進(jìn)去), 即n/2 + 1. 請(qǐng)注意: Manacher算法第一步所做的填充, 其神奇之處在這里開(kāi)始顯現(xiàn), 因?yàn)閺奶畛浜蟮淖址姓页龅淖铋L(zhǎng)回文字符串的長(zhǎng)度也一定是奇數(shù), 并且radius-1就是原始字符串中回文字符串的長(zhǎng)度, 比如:

原字符串是"bbad", 我們可以找到的最長(zhǎng)回文字符串是長(zhǎng)度為2(偶數(shù))的"bb"

而由于填充之后的字符串是"#b#b#a#d#", 所以我們可以找到的最長(zhǎng)回文字符串就變成了長(zhǎng)度為5(奇數(shù))的"#b#b#" (半徑為3, 減1恰好等于2)

原字符串是"cabad", 我們可以找到的最長(zhǎng)回文字符串是長(zhǎng)度為3(奇數(shù))的"aba"

而由于填充之后的字符串是"#c#a#b#a#d#", 所以我們可以找到的最長(zhǎng)回文字符串就變成了長(zhǎng)度為7(仍為奇數(shù))的"#a#b#a#" (半徑為4, 減1恰好等于3)

數(shù)組P: 構(gòu)造一個(gè)數(shù)組P, 用于記錄字符數(shù)組中每個(gè)元素以其為中點(diǎn)可以形成的最大回文字符串的半徑

rPoint: right point, 它是指當(dāng)前有效回文字符串的右端字符的下標(biāo)+1(注意我們是從左端開(kāi)始檢查的), rPoint = mPoint+P[mPoint].?rPoint的作用是利用回文字符串的特性, 減少不必要的檢查, 后面會(huì)詳述. rPoint的初始值是0, 它會(huì)逐漸右移

Manacher算法開(kāi)始:

第一步, 初始化:

令?i = 0 (當(dāng)前檢查的字符下標(biāo)), mPoint=0, rPoint = 0

第二步:

判斷不等式①i < rPoint , 亦即確認(rèn)當(dāng)前檢查的字符是否落在了當(dāng)前有效回文字符串內(nèi)

如果不等式①不成立, 說(shuō)明當(dāng)前還沒(méi)有找到回文字符串, 或者當(dāng)前有效回文字符串的半徑沒(méi)有覆蓋到當(dāng)前檢查的字符, 則令radius?= 1開(kāi)始檢查, 由于radius?= 1, 即只包含當(dāng)前元素本身, 必然立即找到以當(dāng)前字符為中點(diǎn)第一個(gè)回文字符串(即它自己), 更新P[i] = 1

如果不等式①成立, 說(shuō)明之前的檢查已經(jīng)找到了當(dāng)前有效回文字符串, 并且其半徑覆蓋到了當(dāng)前檢查的字符,?也可以說(shuō)當(dāng)前檢查的字符落在了當(dāng)前有效回文字符串內(nèi)

那么?i 一定有一個(gè)關(guān)于當(dāng)前有效回文字符串的中點(diǎn)即?mPoint?的對(duì)稱(chēng)點(diǎn), 我們稱(chēng)它為?j

作為同在當(dāng)前有效回文字符串內(nèi)的兩個(gè)對(duì)稱(chēng)點(diǎn), 在不超出當(dāng)前有效回文字符串的左右兩端的前提下, 注意這里要強(qiáng)調(diào)不超出,?我們不難想象, 如果以?j?為中點(diǎn)可以形成一個(gè)回文字符串, 那么一定也可以以 i 為中點(diǎn)形成一個(gè)相同的回文字符串(否則就不對(duì)稱(chēng), 當(dāng)前有效回文字符串就不可能存在).

于是我們可以整理下目前已經(jīng)直接或者間接知道的事實(shí):

(1) P[j]中已經(jīng)存儲(chǔ)了以 j 這個(gè)元素為中點(diǎn)可以形成的最長(zhǎng)回文字符串半徑

(2) 當(dāng)前有效回文字符串是以mPoint為中心可以形成的最長(zhǎng)回文字符串, 也就是說(shuō)以mPoint為中心, 不可能再有更長(zhǎng)的回文字符串, 并且其半徑已經(jīng)存儲(chǔ)在了P[mPoint]中

(3) 如果回文字符串內(nèi)部對(duì)稱(chēng)位置上有兩個(gè)回文子串, 那么這兩個(gè)回文子串必然是相同的

進(jìn)而我們可以有以下推導(dǎo)(請(qǐng)讀者不妨拿出筆和紙畫(huà)一畫(huà)線(xiàn)段圖, 幫助理解):

a. 當(dāng)?P[j]>rPoint-i?時(shí), 也就是說(shuō)以 j 這個(gè)元素為中點(diǎn)形成的最長(zhǎng)回文字符串足以延伸至當(dāng)前有效回文字符串左端以外時(shí), 則一定有P[i] = rPoint-i, 因?yàn)槿绻?b>P[i] > rPoint-i, 說(shuō)明以 i 這個(gè)元素為中點(diǎn)形成的最長(zhǎng)回文字符串足以延伸至當(dāng)前有效回文字符串右端以外, 那么當(dāng)前有效回文字符串就應(yīng)該有更長(zhǎng)的半徑, 但這與事實(shí)(2)矛盾了. 而如果P[i] < rPoint-i, 則在當(dāng)前有效回文字符串內(nèi)部就會(huì)出現(xiàn)不對(duì)稱(chēng)使其不能成為回文字符串, 這同樣產(chǎn)生矛盾.

b. 當(dāng)P[j]<rPoint-i時(shí), 也就是說(shuō)以 j 這個(gè)元素為中點(diǎn)形成的最長(zhǎng)回文字符串完全被包裹在當(dāng)前有效回文字符串內(nèi)部時(shí), 則一定有P[i] = P[j], 否則它與事實(shí)(3)矛盾

以上兩種情況就可以直接得出P[i], 無(wú)需任何檢查!

c. 當(dāng)P[j] = rPoint-i時(shí)呢? 這時(shí)只能確定P[i]應(yīng)至少等于rPoint-i, 否則會(huì)與事實(shí)(3)矛盾, 可是P[i]可以更大, 這時(shí)我們才需要令radius=rPoint-i開(kāi)始檢查(這就比令radius?= 1開(kāi)始檢查高效)

以當(dāng)前元素為中點(diǎn), 半徑為radius開(kāi)始檢查回文字符串, 如果是回文字符串則擴(kuò)展半徑radius, 嘗試尋找更長(zhǎng)的回文字符串, 直至失敗

此時(shí)要滿(mǎn)足兩個(gè)條件:

②擴(kuò)展半徑之后, 左端和右端的下標(biāo)不越界.

③當(dāng)前左端和右端的元素字符相同.

如果條件②和③都成立,則P[i] = P[i] + 1

緊接著判斷不等式④i+P[i] > rPoint

如果④成立, 說(shuō)明當(dāng)前回文字符串的右端已經(jīng)延伸到了更靠右的位置, 即產(chǎn)生新的當(dāng)前有效回文字符串

立即更新mPoint為當(dāng)前的 i , rPoint為i+P[i]

mPoint=i

rPoint=i+P[i]

如果P[i]比已知的最大回文字符串半徑都大, 記錄并更新最大半徑(根據(jù)最終需求結(jié)果不同也可能是記錄mPoint和rPoint的下標(biāo)),?

循環(huán)執(zhí)行直至②或③不成立

第三步

i?自增, 重復(fù)執(zhí)行第二步,?直至?i?到達(dá)字符數(shù)組的最有端(當(dāng)然如果從?i?的位置不可能再找到比當(dāng)前最長(zhǎng)回文字符串更長(zhǎng)的回文字符串時(shí),?就可以提前結(jié)束)