Manacher 馬拉車算法

5. 最長回文子串 - 力扣（LeetCode）

馬拉車算法是目前解決尋找字符串中最長的回文子串時間復雜度最低的算法（線性O(n)）.

中心擴散法

初始化一個長度與字符串 s 相等的 臂長數組 arr 和 最長臂長 max 與 最長臂長回文串中心下標 maxIndex , 對字符串 s 進行迭代 , 初始化兩個指針 left 和 right 分別指向當前位置 i 的兩邊 , 以判斷當前位置字符的左右字符是否相等 和 左右下標是否超過數組邊界 , 若相等且不超過邊界則指針向外擴散并再次判斷 . 退出判斷后檢測更新 max 和 maxIndex .

原始的中心擴散法只能處理奇數回文串中心的情況 . 因此需要對原始字符串進行映射擴充 : 在開頭 , 結尾以及字符之間插入任意一個相同的 , 非字符串可能存在的字段的特殊字符 ( 一般為 # ) , 這樣字符串的長度由 n 映射到 2*n+1 , 如果出現偶數回文串中心的情況 , 映射到新字符串則是落在特殊字符上 , 最后還原即可 , 這樣保證了對字符串臂長的計算均建立在奇數中心的情況 .

觀察最壞情況 : 字符串每個字符均相同 , 長度為 n , 則對于每個字符串均需要左右指針擴散計算 , 從 0 次 到 n/2 次 再到 0 次 , 得到計算次數大致為 n^2/4 次 , 時間復雜度為 O(n^2) .

import java.util.StringJoiner;
class Solution {public String longestPalindrome(String s) {int n = s.length();StringJoiner sj = new StringJoiner("#", "#", "#");for(int i = 0; i < n; ++i) {sj.add(s.substring(i, i + 1));}int number = sj.toString().length();char[] charArr = sj.toString().toCharArray();int[] arr = new int[number];int max = 0;int maxIndex = 0;int left, right;for(int i = 0; i < number; ++i) {left = i - 1;right = i + 1;while(left >= 0 && right < number) {if(charArr[left] == charArr[right]){++arr[i];--left;++right;}else break;}if(arr[i] > max) {max = arr[i];maxIndex = i;}}max = (max - 1) / 2;if((maxIndex - 1) % 2 == 1) { // 偶數中心maxIndex = (maxIndex - 1) / 2;return s.substring(maxIndex - max, maxIndex + max + 2);}maxIndex = (maxIndex - 1) / 2;return s.substring(maxIndex - max, maxIndex + max + 1);}
}

Manacher 對中心擴散法的優化

中心擴散法對每個字符進行計算明顯具有冗余 , Manacher 馬拉車算法的目的即是盡可能的減少計算 , 降低時間復雜度 : 注意到回文串的臂長具有 對稱性 : 回文串以中心點為對稱軸 , 其左右兩側的字符是相等的 , 回文串最遠距離內任意非中心字符的臂長可以繼承對應字符的臂長 . 為了實現這一便利 , 我們需要在每次迭代時額外維護兩個量 最右邊界r 和 最右邊界對應的大回文串中心centerIndex .

arr[i] = Math.min(r - i, arr[2 * centerIndex - i]); 是算法的核心語句 , 可以認為當回文子字符的臂長沒有超過大回文的邊界時 , 我們對該該字符是 完全知悉的 , 臂長在大回文內即被截斷 . 若鏡像點的回文半徑較小以至于其完全包含在以 centerIndex 為中心的大回文串中 , 那么當前字符的回文半徑可以直接繼承完全知悉的鏡像點 arr[2 * centerIndex - i] , 不需要再進行計算 ; 若鏡像點的回文半徑較大以至于超出了大回文串的邊界 , 則當前字符的回文半徑至少可以繼承到大回文的最右邊界right - i , 而我們對大回文外的字符分布并不知悉 , 因此后續需要計算嘗試擴展 .

同樣觀察最壞情況 : 字符串的每個字符均相同 , 對于前半字符串的每個位置 n 需要計算 n-(n-1) 即 1 次 , 后半字符串因為鏡像點始終完全知悉 , 直接繼承即可 , 計算次數也為 1 次 , 總計算次數為 n 次 , 時間復雜度為 O(n) .

class Solution {public String longestPalindrome(String s) {int n = s.length();StringBuilder sb = new StringBuilder();sb.append("#");for(int i = 0; i < n; ++i) {sb.append(s.substring(i, i + 1)).append("#");}int number = sb.toString().length();char[] charArr = sb.toString().toCharArray();int[] arr = new int[number];int max = 0;int maxIndex = 0;int r = maxIndex + max;int centerIndex = 0;int left, right;for(int i = 0; i < number; ++i) {left = i - 1;right = i + 1;if(i <= r) {arr[i] = Math.min(r - i, arr[2 * centerIndex - i]); // Manacher核心語句left -= arr[i];right += arr[i];}while(left >= 0 && right < number && charArr[left] == charArr[right]) {++arr[i];--left;++right;}if(arr[i] > max) {max = arr[i];maxIndex = i;}if(r < arr[i] + i) {r = arr[i] + i;centerIndex = i;}}int start = (maxIndex - max) / 2;int end = start + max;return s.substring(start, end);}
}