layout: post
title: Manacher(馬拉車)演算法
date: 2019-09-07
author: xiepl1997
cover: ‘assets/img/manacher.png’
tags: 敲敲敲
Manacher’s Alogrithm，中文名叫馬拉車演算法，是一位叫Manacher的人在1975年提出的一種演算法，解決的問題是求最長迴文子串，演算法的神奇之處就在於將時間複雜度精進到了O(N)。還記得在兩年前的四省賽中，有一道關於迴文的題，題解就是用馬拉車演算法做解的，然而我們沒有做出來。
01 由來#
在求解最長迴文子串時，一般的思路是以當前字元爲中心向兩邊擴充套件尋找迴文，但複雜度是O(N^2)，那能不能將複雜度降低到線性？馬拉車演算法就是爲此誕生的。
02 預處理#
爲了在處理字串的時候不需要爲字串長度是奇數還是偶數而分別考慮，將對原始字串進行處理，在每一個字元的左右兩邊都加上特殊字元（肯定不存在原始字串中的字元），讓字串變成一個長度爲奇數的字串。如： abba --> #a#b#b#a#
03 計算最長迴文子串長度#
以字串"arddrb"爲例，將預處理後的新字串"#a#r#d#d#r#b#"，作爲一個新的字串arr，定義一個輔助陣列Len，Len的長度與arr等長，用Len[i]來表示以arr[i]字元爲中心的最長迴文半徑。
在等待Len陣列計算出來之後，取Len陣列中值最大的數所對應的下標，就是arr字串中的所對應的字元爲中心的迴文串的半徑，Len陣列有一個特點：Len[i]-1的值，就是原字串中該以該字元爲中心的迴文串的長度。以下爲i、arr、Len對應的值
Copy
i 0 1 2 3 4 5 6 7 8 9 10 11 12
arr # a # r # d # d # r # b #
Len 1 2 1 2 1 2 5 2 1 2 1 2 1
04 計算迴文子串起始索引#
取出Len陣列中最大的值的索引i後，應該如何由得到原字串該字元的索引呢？繼續以str=「arddrb"爲例，有arr=」#a#r#d#d#r#b#"，Len[6]=5，發現6-Len(6)=1，即i-Len[i]就是arr[i]字元在原始字串中的下標。但以str=「aba"爲例，arr=」#a#b#a#"，Len[3]=4，3-Len[3]=-1，所以str[-1]將會溢位。爲了避免奇迴文溢位，所以在arr的首尾再分別新增一個特殊字元，如下
Copy
i 0 1 2 3 4 5 6 7 8 9 10
arr @ # c # a # b # a # $
Len 1 1 2 1 2 1 4 1 2 1 1
可以看出，對於b字元來說，6-Len(6)=2，可以得到最長迴文子串的起始索引爲(i-Len(i))/2。
05 計算Len陣列#
第三步和第四部都是以Len陣列計算完成爲前提來進行的，計算Len陣列就是馬拉車演算法的主要工作了，還是以"arddrb"爲例，
Copy
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
arr @ # a # r # d # d # r # b # $
Len 1 1 2 1 2 1 2 5 2 1 2 1 2 1 1
定義兩個變數Mi和R，Mi是所有迴文子串中，能延伸到最右端位置的那個迴文子串的中心點位置，R是該回文串能延伸到最右端的位置。
當i=7時，Len[i]=5，在以位置7位中心點的迴文子串中，該回文串的右邊界是位置12。
當i=12時，Len[i]=2，在以位置12位元中心點的迴文子串中，該回文串的右邊界是位置14。
所以可以得到，R=Len[i]+i
具體程式設計時，從左往右計算陣列Len，需要分以下情況
1） 當i <= R時，首先毫無疑問Len陣列中i點之前的對應的值已經求出來了，利用迴文的特點，只要找到i關於Mi點對稱的點j，j=Mi* 2-i，i、j在以Mi爲中心的迴文串的範圍內[L, R]：
如果Len[j] < R-i(同樣是L到j的距離)，說明以j爲中心的迴文串沒有超出範圍[L, R]，所以，Len[i] = Len(j)，如下圖
image
如果Len[j] >= R-i，即j爲中心的迴文串的最左端超過L，如下圖所示，所以Len[i] = Len[j]是不成立的，有迴文串的特性可知，Len[i] 至少等於R-i，至於是否大於R-i，那還得需要從R+1開始一一匹配，直到失配爲止，從而更新R和對應的中心點Mi以及Len[i]。
image
2） 當i > R時，如下圖，這種情況沒法用到迴文串的特性，只能老實地去一一匹配。
image
程式碼如下（以leetcode第5題爲例）
Copy
public String longestPalindrome(String s) {
int mi = 0;
int right = 0;
int maxlength = 0;
int maxpoint = 0;
String temp = 「@#」;
for(int i = 0; i < s.length(); i++){
temp += s.charAt(i);
temp += 「#」;
}
temp += "";
int[] p = new int[temp.length()];
for(int i = 0; i < temp.length(); i++){
p[i] = 0;
}
for(int i = 1; i < temp.length()-1; i++){
p[i] = right > i? Math.min(p[2mi-i], right - i) : 1;
while(temp.charAt(i+p[i]) == temp.charAt(i-p[i])){
p[i]++;
}
if(i + p[i] > right){
right = i + p[i];
mi = i;
}
if(maxlength < p[i]){
maxlength = p[i];
maxpoint = i;
}
}
//(maxpoint - maxlength)/2爲最長迴文數的起始點，maxlength爲最長迴文數的長度
return s.substring((maxpoint - maxlength)/2, (maxpoint - maxlength)/2 + maxlength - 1);
}
理解p[i] = right > i? Math.min(p[2* mi-i], right - i) : 1;就將manacher理解的差不多了。