Manacher算法在計算最長回文子串長度中的應用

唐高陽

【摘 要】本文首介紹了如何運用Manacher算法在線性時間內(nèi)找到一個字符串的最長回文子串。

【關(guān)鍵詞】Manacher算法；回文串；回文子串

The Manacher algorithm is used to calculate the length of the longest return string

TANG Gao-yang

（Shenyang institute of science and technology， Shenyang， Liaoning 110168）

【Abstract】This paper first introduces a method for finding the longest palindrome subsrting in linear time by the Manacher Algorithm.

【Key words】Manacher algorithm；Palindrome srting；Palindrome subsrting

1 遍歷

因為奇回文和偶回文在判斷時比較麻煩，所以對str進行處理，把每個字符開頭、結(jié)尾和中間插入一個特殊字符′#′來得到一個新的字符串數(shù)組。比如str=″bcbaa″，處理后為″#b#c#b#a#a#″，然后從每個字符左右擴出去的方式找最大回文子串就方便多了。對奇回文來說，不這么處理也能通過擴的方式找到，比如″bcb″，從′c′開始向左右兩側(cè)擴出去能找到最大回文。處理后為″#b#c#b#″，從′c′開始向左右兩側(cè)擴出去依然能找到最大回文。對偶回文來說，不處理而直接通過擴的方式是找不到的，比如″aa″，因為沒有確定的軸，但是處理后為″#a#a#″，就可以通過從中間的′#′擴出去的方式找到最大回文。所以通過這樣的處理方式，最大回文子串無論是偶回文還是奇回文，都可以通過統(tǒng)一的“擴”過程找到，解決了差異性的問題。同時要說的是，這個特殊字符是什么無所謂，甚至可以是字符串中出現(xiàn)的字符，也不會影響最終的結(jié)果，就是一個純輔助的作用。

具體的處理過程請參看如下代碼中的manacherString方法。

public char[] manacherString（String str） {

char[] charArr=str.toCharArray（）；

char[] res=new char[str.length（）*2+1]；

int index=0；

for （i=0；I ！=res.length；i++）{

res[i]=（i&1）==0？#：charArr[index++]；

}

Return res；

}

2 優(yōu)化

假設str處理之后的字符串記為charArr。對每個字符（包括特殊字符）都進行“優(yōu)化后”的擴過程。

3 擴過程

只要能夠從左到右依次算出數(shù)組pArr每個位置的值，最大的那個值實際上就是處理后的charArr中最大的回文半徑，根據(jù)最大的回文半徑，再對應回原字符串的話，整個問題就解決了。步驟3就是從左到右依次計算出pArr數(shù)組每個位置的值的過程。

（1）假設現(xiàn)在計算到位置i的字符charArr[i]，在i之前位置的計算過程中，都會不斷地更新pR和index的值，即位置i之前的index這個回文中心擴出了一個目前最右的回文邊界pR。

（2）如果pR-1位置沒有包住當前的i位置。比如“#c#a#b#a#c#”，計算到charArr[1]==c時，pR為1。也就是說，右邊界在1位置，1位置為最右回文半徑即將到達但還沒有達到的位置，所以當前的pR-1位置沒有包住當前的i位置。此時和普通做法一樣，從i位置字符開始，向左右兩側(cè)擴出去檢查，此時的“擴”過程沒有獲得加速。

（3）如果pR-1位置包住當前的i位置。比如“#c#a#b#a#c#”，計算到charArr[6…10]時，pR都為11，此時pR-1包住了位置6-10。這種情況下，檢查過程是可以獲得優(yōu)化的，這也是manacher算法的核心內(nèi)容。

4 進階問題

按照步驟3的邏輯從左到右計算出pArr數(shù)組，計算完成后再遍歷一遍pArr數(shù)組，找出最大的回文半徑，假設位置i的回文半徑最大，即pArr[i]==max。但max只是charArr的最大回文半徑，還得對應回原來的字符串，求出最大回文半徑的長度（其實就是max-1）。在charArr中位置3的回文半徑最大，最大值為4（即pArr[3]==4），對應原字符串的最大回文子串長度為4-1=3。

Manacher算法時間復雜度是O（N）的證明。雖然我們可以很明顯地看到Manacher算法與普通方法相比，在擴出去檢查這一行為上有明顯的優(yōu)化，但如何證明該算法的時間復雜度就是O（N）呢？關(guān)鍵之處在于估算擴出去檢查這一行為發(fā)生的數(shù)量。原字符串在處理后的長度由N變?yōu)?N，從步驟3的主要邏輯來看，要么在計算一個位置的回文半徑時完全不需要擴出去檢查，比如，步驟3的中3）介紹的情況一和情況二，都可以直接獲得位置i的回文半徑長度；要么每一次擴出去檢查都會讓回文半徑到達更右的位置，當然會使pR更新。然而pR最多是從-1增加到2N（右邊界），并且從來不減小，所以擴出去檢查的次數(shù)就是O（N）的級別。所以Manacher算法時間復雜度是O（N）。具體請參看如下代碼中的maxLcpsLength方法。

public static int maxLcpsLength（String str） {

if （str == null || str.length（） == 0） {endprint

return 0；

}

char[] charArr = manacherString（str）；

int[] pArr = new int[charArr.length]；

int index = -1；

int pR = -1；

int max = Integer.MIN_VALUE；

for （int i = 0； i ！= charArr.length； i++） {

pArr[i] = pR > i ？ Math.min（pArr[2 * index - i]， pR - i） ： 1；

while （i + pArr[i] < charArr.length && i - pArr[i] > -1） {

if （charArr[i + pArr[i]] == charArr[i - pArr[i]]）

pArr[i]++；

else {

break；

}

}

if （i + pArr[i] > pR） {

pR = i + pArr[i]；

index = i；

}

max = Math.max（max， pArr[i]）；

}

return max - 1；

}

在字符串的最后添加最少字符，使整個字符串都成為回文串，其實就是查找在必須包含最后一個字符的情況下，最長的回文串是什么。那么之前不是最長回文子串的部分逆序過來，就是應該添加的部分。比如“abcd123321”，在必須包含最后一個字符的情況下，最長的回文子串是 “123321”，之前不是最長回文子串的部分是“abcd”，所以末尾應該添加的部分就是“dcba”。那么只要把manacher算法稍作修改就可以。具體改為：從左到右計算回文半徑時，關(guān)注回文半徑最右即將到達的位置（pR），一旦發(fā)現(xiàn)已經(jīng)到達最后（pR == charArr.length），說明必須包含最后一個字符的最長回文半徑已經(jīng)找到，直接退出檢查過程，返回該添加的字符串即可。具體過程參看如下代碼中的shortestEnd方法。

public static String shortestEnd（String str） {

if （str == null || str.length（） == 0） {

return null；

}

char[] charArr = manacherString（str）；

int[] pArr = new int[charArr.length]；

int index=-1；

int pR=-1；

int maxContainsEnd = -1；

for （int i = 0； i ！= charArr.length； i++） {

pArr[i] = pR > i ？ Math.min（pArr[2 * index - i]， pR - i） ： 1；

while （i + pArr[i] < charArr.length && i - pArr[i] > -1） {

if （charArr[i + pArr[i]] == charArr[i - pArr[i]]）

pArr[i]++；

else {

break；

}

}

if （i + pArr[i] > pR） {

pR = i + pArr[i]；

index = i；

}

if （pR == charArr.length） {

maxContainsEnd = pArr[i]；

break；

}

}

char[] res = new char[str.length（） - maxContainsEnd + 1]；

for （int i = 0； i < res.length； i++） {

res[res.length - 1 - i] = charArr[i * 2 + 1]；

}

return String.valueOf（res）；

}

5 結(jié)果與分析

Manacher算法是由Glenn Manacher于1975年首次發(fā)明的，比起能夠解決該問題的其他算法，Manacher算法算比較好理解和實現(xiàn)的。

【參考文獻】

[1]Bruce Eckel.《Java編程思想》.機械工業(yè)出版社.2007.6.1.

[2]梁勇.《Java語言程序設計（基礎篇）》.機械工業(yè)出版社2015.7.1.

[3]梁勇.《Java語言程序設計（進階篇）》.機械工業(yè)出版社.2016.10.1.

[4]Thomas H.Cormen；Charles E.Leiserson；Ronald L.Rivest；Clifford Stein 《算法導論》機械工業(yè)出版社.2013.7.1.

[5]Mark Allen Weiss.《數(shù)據(jù)結(jié)構(gòu)與算法分析 Java語言描述》.機械工業(yè)出版社.2009.1.1.

[6]Robert Sedgewick. Kevin Wayne.《算法（第4版）》人民郵電出版社.2012.10.1.endprint