Manacher算法的詳細講解

Manacher算法

Manacher算法：在一個字元串中找到最長回文串。

回文：正着念和反着念一樣的東西。“121”,“1221”.

第一種方法: 暴力解，時間複雜度O(n*n)。分為兩種情況:

思路

從一個位置 i 開始向兩邊擴，i 位置肯定自己就可以構成回文，繼續看 i-1 位置和 i+1 位置是否相等，若相等，則以 i 為中心的字元就擴出來了3個，繼續看 i-2 與 i+2 位置…，即：以一個字元為中心向兩邊擴，奇數長度可以，但偶回文怎麼辦？舉例子： 1221,都無法擴

解決：向整個字元串的兩頭及中間加一個特征字元，讓無論是奇長度還是偶長度的字元串都可以變成奇長度，最後原始字元串最長回文子串的長度為 最大值/2；

該字元串最長回文子串的長度=11/2=5.

注：中間加的特殊字元可任意加，因為 虛軸永遠之和虛軸比，虛軸不可能和實軸比。

第二種方法: Manacher，時間複雜度O(n)。

講述Manacher算法之前，我們要先建立幾個概念：

• 回文直徑：以一個位置為中心向兩邊擴，擴出來的整個串的長度。

• 回文半徑：一個串開始擴，擴一半的長度。

  這裡，我們需要一個輔助數組–回文半徑數組：該數組記錄從左往右依次開始以每個位置為中心的情況下能夠擴出來的回文半徑的長度，我們看計算後邊的回文半徑過程能不能利用前邊計算好的回文半徑的結論進行加速。

• 最右回文右邊界：所有回文半徑中最靠右的位置(用R表示)。

舉個例子說明吧：

一開始，最右回文右邊界R 是在 -1 位置，無效值。當從 0 位置擴時，隻能擴到它自己，是以 R=0；擴 1 時，1 沒在回文右邊界裡，發現從 1 擴時可以擴到 2 位置，是以 R=2，當擴 2 位置上的 ‘#’ 時，隻能擴到它自己，是以 R=2， 當擴 3 位置的 ‘2’ 時，R=6，即對比字元串，來到的最右位置就就叫做所有回文半徑中的回文右邊界，擴 4,5 位置時，R 都沒有再擴出去，如果沒有擴出去，那回文右邊界就一直停在 6，直到來到 6 位時，停。

• 回文右邊界中心：當到達一個回文右邊界時，它對應的中心位置(用C表示)。

  

它倆永遠是相伴随的，即： 隻要 回文右邊界R 沒更新，就記錄下最早到達回文右邊界的位置時，其中心C 在哪。

由于可能有多個都能到達同樣的R，例如 “1213121”，當到達 3位置 時，R=6，到 4位置 時，R=6，則我們的 C 就記錄的是 R 第一次到達6位置時的中心點位置，如果 R 更往又了，則 C 應該改變。

我們的Manacher就是建立在這幾個概念上玩出來的~~

現在開始講Manacher

Manacher算法其實和暴力解法是非常像的，隻是在擴的過程中有加速而已。

為了解起來較為直覺容易，我們将出現的情況分為四大類：

第一種可能性: i 不在回文右邊界裡

假設目前來到的是 i 位置，我們以 i 作為中心向兩邊擴，看能擴多長。

eg：

擴 0 位置時， R=-1，這就叫 i 不在回文右邊界裡。

注：二三四中可能性都是建立在一種可能性上的，即： i 位置在回文右邊界裡

根據 i 做關于 C 的對稱點 i’，i’ 的回文半徑的具體情況拆分了3種可能性

數組中每個位置為回文半徑長度，記錄 i’ 的回文區域。

接下來我們依次分析這三種情況：

第二種可能性: i’ 的回文區域整體都在 (L 與 R) 内

i 位置的回文區域不用擴，直接知道答案：和 i’ 一樣（證明可用反證法）

第三種可能性: i’ 的回文子串的左區域在 L 外

此時， i 的回文半徑就是 i到R（證明可用反證法）

第四種可能性: i’ 的回文半徑與L壓線

此時從 L 到 R 不用驗，但是隻有能不能擴的更大還需要再繼續擴

由于：回文最右右邊界R 隻能往右推，不能往左縮，即：直接擴成功，R都在增加，R最多也就是從字元串左推到右，由于可能性2和3不用計算，直接知道答案，時間複雜度O(1)；是以隻有可能性1與4 的代價使R從最左到最右，是以總時間複雜度為O（n），

最後附上代碼：

public class Manacher {

	public static char[] manacherString(String str) {
		char[] charArr = str.toCharArray();
		char[] res = new char[str.length() * 2 + 1];
		int index = 0;
		for (int i = 0; i != res.length; i++) {
			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
		}
		return res;
	}

	public static int maxLcpsLength(String str) {
		if (str == null || str.length() == 0) {
			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;
	}

	public static void main(String[] args) {
		String str1 = "abc1234321ab";
		System.out.println(maxLcpsLength(str1));
	}
}
           

Manacher算法就是這樣子的哦~~