唐高陽
【摘 要】本文首介紹了如何運用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