最長(zhǎng)回文串問(wèn)題是一個(gè)經(jīng)典的算法題。
0. 問(wèn)題定義
最長(zhǎng)回文子串問(wèn)題：給定一個(gè)字符串，求它的最長(zhǎng)回文子串長(zhǎng)度。
如果一個(gè)字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實(shí)例：
12321 a aba abba aaaa tattarrattat（牛津英語(yǔ)詞典中最長(zhǎng)的回文單詞）
1. Brute-force解法
對(duì)于最長(zhǎng)回文子串問(wèn)題，最簡(jiǎn)單粗暴的辦法是：找到字符串的所有子串，遍歷每一個(gè)子串以驗(yàn)證它們是否為回文串。一個(gè)子串由子串的起點(diǎn)和終點(diǎn)確定，因此對(duì)于一個(gè)長(zhǎng)度為n的字符串，共有n2個(gè)子串。這些子串的平均長(zhǎng)度大約是n/2，因此這個(gè)解法的時(shí)間復(fù)雜度是O(n3)。
2. 改進(jìn)的方法
顯然所有的回文串都是對(duì)稱(chēng)的。長(zhǎng)度為奇數(shù)回文串以最中間字符的位置為對(duì)稱(chēng)軸左右對(duì)稱(chēng)，而長(zhǎng)度為偶數(shù)的回文串的對(duì)稱(chēng)軸在中間兩個(gè)字符之間的空隙?？煞窭眠@種對(duì)稱(chēng)性來(lái)提高算法效率呢？答案是肯定的。我們知道整個(gè)字符串中的所有字符，以及字符間的空隙，都可能是某個(gè)回文子串的對(duì)稱(chēng)軸位置。可以遍歷這些位置，在每個(gè)位置上同時(shí)向左和向右擴(kuò)展，直到左右兩邊的字符不同，或者達(dá)到邊界。對(duì)于一個(gè)長(zhǎng)度為n的字符串，這樣的位置一共有n+n-1=2n-1個(gè)，在每個(gè)位置上平均大約要進(jìn)行n/4次字符比較，于是此算法的時(shí)間復(fù)雜度是O(n^2)。
3. Manacher 算法
對(duì)于一個(gè)比較長(zhǎng)的字符串，O(n^2)的時(shí)間復(fù)雜度是難以接受的。Can we do better?
先來(lái)看看解法2存在的缺陷。
1)由于回文串長(zhǎng)度的奇偶性造成了不同性質(zhì)的對(duì)稱(chēng)軸位置，解法2要對(duì)兩種情況分別處理；
2)很多子串被重復(fù)多次訪問(wèn)，造成較差的時(shí)間效率。
缺陷2）可以通過(guò)這個(gè)直觀的小??體現(xiàn)：
char: a b a b a
i : 0 1 2 3 4```
當(dāng)i==1，和i==2時(shí)，左邊的子串a(chǎn)ba分別被遍歷了一次。
如果我們能改善**解法2**的不足，就很有希望能提高算法的效率。Manacher正是針對(duì)這些問(wèn)題改進(jìn)算法。
**(1) 解決長(zhǎng)度奇偶性帶來(lái)的對(duì)稱(chēng)軸位置問(wèn)題。**
Manacher算法首先對(duì)字符串做一個(gè)預(yù)處理，在所有的空隙位置(包括首尾)插入同樣的符號(hào)，要求這個(gè)符號(hào)是不會(huì)在原串中出現(xiàn)的。這樣會(huì)使得所有的串都是奇數(shù)長(zhǎng)度的。以插入#號(hào)為例：
```tex
aba ---> #a#b#a#
abba ---> #a#b#b#a#
插入的是同樣的符號(hào)，且符號(hào)不存在于原串，因此子串的回文性不受影響，原來(lái)是回文的串，插完之后還是回文的，原來(lái)不是回文的，依然不會(huì)是回文。
(2)解決重復(fù)訪問(wèn)的問(wèn)題。
我們把一個(gè)回文串中最左或最右位置的字符與其對(duì)稱(chēng)軸的距離稱(chēng)為回文半徑。Manacher定義了一個(gè)回文半徑數(shù)組RL，用RL[i]表示以第i個(gè)字符為對(duì)稱(chēng)軸的回文串的回文半徑。我們一般對(duì)字符串從左往右處理，因此這里定義RL[i]為第i個(gè)字符為對(duì)稱(chēng)軸的回文串的最右一個(gè)字符與字符i的距離。對(duì)于上面插入分隔符之后的兩個(gè)串，可以得到RL數(shù)組：
char: # a # b # a #
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i : 0 1 2 3 4 5 6
char: # a # b # b # a #
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i : 0 1 2 3 4 5 6 7 8
上面我們還求了一下RL[i]-1。通過(guò)觀察可以發(fā)現(xiàn)，RL[i]-1的值，正是在原本那個(gè)沒(méi)有插入過(guò)分隔符的串中，以位置i為對(duì)稱(chēng)軸的最長(zhǎng)回文串的長(zhǎng)度。那么只要我們求出了RL數(shù)組，就能得到最長(zhǎng)回文子串的長(zhǎng)度。
于是問(wèn)題變成了，怎樣高效地求的RL數(shù)組。基本思路是利用回文串的對(duì)稱(chēng)性，擴(kuò)展回文串。
我們?cè)僖胍粋€(gè)輔助變量MaxRight，表示當(dāng)前訪問(wèn)到的所有回文子串，所能觸及的最右一個(gè)字符的位置。另外還要記錄下MaxRight對(duì)應(yīng)的回文串的對(duì)稱(chēng)軸所在的位置，記為pos，它們的位置關(guān)系如下。
我們從左往右地訪問(wèn)字符串來(lái)求RL，假設(shè)當(dāng)前訪問(wèn)到的位置為
i，即要求RL[i]，在對(duì)應(yīng)上圖，i必然是在po右邊的(obviously)。但我們更關(guān)注的是，i是在MaxRight的左邊還是右邊。我們分情況來(lái)討論。
1）當(dāng)i在MaxRight的左邊；
情況1)可以用下圖來(lái)刻畫(huà)：
我們知道，圖中兩個(gè)紅色塊之間（包括紅色塊）的串是回文的；并且以
i為對(duì)稱(chēng)軸的回文串，是與紅色塊間的回文串有所重疊的。我們找到i關(guān)于pos的對(duì)稱(chēng)位置j，這個(gè)j對(duì)應(yīng)的RL[j]我們是已經(jīng)算過(guò)的。根據(jù)回文串的對(duì)稱(chēng)性，以i為對(duì)稱(chēng)軸的回文串和以j為對(duì)稱(chēng)軸的回文串，有一部分是相同的。這里又有兩種細(xì)分的情況。a. 以
j為對(duì)稱(chēng)軸的回文串比較短，短到像下圖這樣。
這時(shí)我們知道RL[i]至少不會(huì)小于RL[j]，并且已經(jīng)知道了部分的以
i為中心的回文串，于是可以令RL[i]=RL[j]。但是以i為對(duì)稱(chēng)軸的回文串可能實(shí)際上更長(zhǎng)，因此我們?cè)囍?code>i為對(duì)稱(chēng)軸，繼續(xù)往左右兩邊擴(kuò)展，直到左右兩邊字符不同，或者到達(dá)邊界。b. 以
j為對(duì)稱(chēng)軸的回文串很長(zhǎng)，這么長(zhǎng)：
這時(shí)，我們只能確定，兩條藍(lán)線之間的部分（即不超過(guò)MaxRight的部分）是回文的，于是從這個(gè)長(zhǎng)度開(kāi)始，嘗試以
i為中心向左右兩邊擴(kuò)展，，直到左右兩邊字符不同，或者到達(dá)邊界。不論以上哪種情況，之后都要嘗試更新
MaxRight和pos，因?yàn)橛锌赡艿玫礁蟮腗axRight。具體操作如下：
step 1: RL[i] <--- min(RL[2*pos-i], MaxRight-i)
step 2: 以i為中心擴(kuò)展回文串，直到左右兩邊字符不同，或者到達(dá)邊界。
step 3: 更新MaxRight和pos
2）當(dāng)i在MaxRight的右邊。
遇到這種情況，說(shuō)明以
i為對(duì)稱(chēng)軸的回文串還沒(méi)有任何一個(gè)部分被訪問(wèn)過(guò)，于是只能從i的左右兩邊開(kāi)始嘗試擴(kuò)展了，當(dāng)左右兩邊字符不同，或者到達(dá)字符串邊界時(shí)停止。然后更新MaxRight和pos。(3)算法實(shí)現(xiàn)
def manacher(s):
#預(yù)處理
s='#'+'#'.join(s)+'#'
RL=[0]*len(s)
MaxRight=0
pos=0
MaxLen=0
for i in range(len(s)):
if i<MaxRight:
RL[i]=min(RL[2*pos-i], MaxRight-i)
else:
RL[i]=1
#嘗試擴(kuò)展，注意處理邊界
while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
RL[i]+=1
#更新MaxRight,pos
if RL[i]+i-1>MaxRight:
MaxRight=RL[i]+i-1
pos=i
#更新最長(zhǎng)回文串的長(zhǎng)度
MaxLen=max(MaxLen, RL[i])
return MaxLen-1
(4)復(fù)雜度分析
空間復(fù)雜度：插入分隔符形成新串，占用了線性的空間大?。籖L數(shù)組也占用線性大小的空間，因此空間復(fù)雜度是線性的。
時(shí)間復(fù)雜度：盡管代碼里面有兩層循環(huán)，通過(guò)amortized analysis我們可以得出，Manacher的時(shí)間復(fù)雜度是線性的。由于內(nèi)層的循環(huán)只對(duì)尚未匹配的部分進(jìn)行，因此對(duì)于每一個(gè)字符而言，只會(huì)進(jìn)行一次，因此時(shí)間復(fù)雜度是O(n)。
4. 更多關(guān)于回文串的fun facts（主要來(lái)自維基百科）
4.1 人們?cè)谝蛔麨楹諑?kù)蘭尼姆的古城遺跡中，找到了一個(gè)好玩的拉丁語(yǔ)回文串：sator arepo tenet opera rotas。翻譯成中文大概就是`一個(gè)叫做Arepo的播種者，他用力地扶（把）著車(chē)輪。這個(gè)串的每個(gè)單詞首字母剛好組成了第一個(gè)單詞，每個(gè)單詞的第二個(gè)字母剛好組成了第二個(gè)單詞...于是乎，如果寫(xiě)出醬紫，你會(huì)發(fā)現(xiàn)上下左右四個(gè)方向讀起來(lái)是一樣的。這個(gè)串被稱(chēng)為 Sator Square.
4.2 本文開(kāi)頭給出的單詞tattarrattat，出現(xiàn)在愛(ài)爾蘭作家詹姆斯·喬伊斯的小說(shuō)《尤利西斯》，是敲門(mén)的意思。吉尼斯紀(jì)錄的最長(zhǎng)回文英文單詞是detartrated，是個(gè)化學(xué)術(shù)語(yǔ)。另外，還有些已出版的英文回文小說(shuō)（你們歪果仁真會(huì)玩），比如Satire: Veritas，Dr Awkward & Olson in Oslo等。
本文遵守知識(shí)共享協(xié)議：署名-非商業(yè)性使用-相同方式共享 (BY-NC-SA)及簡(jiǎn)書(shū)協(xié)議轉(zhuǎn)載請(qǐng)注明：作者曾會(huì)玩
2015.11.9 更新。
可以采用動(dòng)態(tài)規(guī)劃，列舉回文串的起點(diǎn)或者終點(diǎn)來(lái)解最長(zhǎng)回文串問(wèn)題，無(wú)需討論串長(zhǎng)度的奇偶性。
看下面的扎瓦代碼，容易理解。
public int longestPalindrome(String s) {
int n=s.length();
boolean[][] pal=new boolean[n][n];
//pal[i][j] 表示s[i...j]是否是回文串
int maxLen=0;
for (int i=0;i<n;i++){ // i作為終點(diǎn)
int j=i; //j作為起點(diǎn)
while (j>=0){
if (s.charAt(j)==s.charAt(i)&&(i-j<2||pal[j+1][i-1])){
pal[j][i]=true;
maxLen=Math.max(maxLen, i-j+1);
}
j--;
}
}
return maxLen;
}
