針對最長迴文子串相關的問題，馬拉車算法應該是比較通用的解法，今天我們就來具體看看這個算法。
簡介
馬拉車算法(Manacher‘s Algorithm)是用來查找一個字符串的最長迴文子串的線性方法，由一個叫 Manacher 的人在1975年發明的，這個方法的最大貢獻是在於將時間複雜度提升到了線性。
這個算法最厲害的地方是在於能夠在線性時間內解決問題。一般我們解決最長迴文子串，不可避免都要進行回溯之類的操作，那麼時間複雜度一定是大於線性的。
而馬拉車算法的主要思路是維護一個跟原字符串 str 長度一樣的數組 lens，lens[i] 表示以 str[i] 為中點的回串其中一邊的長度。
在這裡，有的人把中點算進去，有的人記錄兩邊的長度，其實都是一樣的。我在這裡是只記錄一邊的長度，不包括中點。比如CDCDE：
<code>str: [C, D, C, D, E]
lens: [0, 1, 1, 0, 0]
/<code>
那麼 lens 裡最大的自然就對應最長回串的中點了。所以這個算法的核心就是如何快速計算 lens。
具體思路
預處理
迴文有奇偶長度兩種情況，通過補充間隔符可以將這兩種情況化簡為奇數長度。
比如：
ABA補充為^#A#B#A#$，中點還是 B。 ABBA補充為^#A#B#B#A#$，中點為 #，最後可以去掉。
針對間隔符，首先要確保在字符串中不會出現，這裡我是確保字符串中不會出現^、#、$。
原字符串中每一個字符都會被#包圍，這樣就確保現在的字符串長度一定是奇數。
至於在開頭增加^，在結尾增加$，這樣是為了確保從任意一個位置開始檢查迴文時，一定會遇到不一樣的時候，從而退出循環。而且也方便我們計算原字符的下標，直接除以2即可。
寫法是：
<code> String str = "cbcbccde";
char[] T = new char[str.length() * 2 + 3];
T[0] = '^';
T[1] = '#';
T[T.length - 1] = '$';
for (int i = 0; i < str.length(); i++) {
char charStr = str.charAt(i);
T[2 * i + 2] = charStr;
T[2 * i + 3] = '#';
}
/<code>
計算長度數組
這就是算法的關鍵了，它充分利用了迴文串的對稱性。
我們用 C 表示迴文串的中心，用 R 表示迴文串的右邊半徑。所以 R = C + P[ i ] 。C 和 R 所對應的迴文串是當前循環中 R 最靠右的迴文串。用 i_mirror 表示當前需要求的第 i 個字符關於 C 對應的下標。
讓我們考慮求 P [ i ] 的時候：
我們可以利用迴文串 C 的對稱性。i 關於 C 的對稱點是 i_mirror ，P [ i_mirror ] = 3，所以 P [ i ] 也等於 3 。
但需要考慮特殊情況：
P [ i_mirror ] + i >= R
如下圖：
當我們要求 P [ i ] 的時候，P [ mirror ] = 7，而此時 P [ i ] 並不等於 7 ，為什麼呢，因為我們從 i 開始往後數 7 個，等於 22 ，已經超過了最右的 R ，此時不能利用對稱性了，但我們一定可以擴展到 R 的，所以 P [ i ] 至少等於 R - i = 20 - 15 = 5，會不會更大呢，我們只需要比較 T [ R+1 ] 和 T [ R+1 ]關於 i 的對稱點就行了，就像中心擴展法一樣一個個擴展。
i_mirror - P [ i_mirror ] == 0
如下圖：
此時P [ i_mirror ] = 1，但是 P [ i ] 賦值成 1 是不正確的，出現這種情況的原因是 P [ i_mirror ] 在擴展的時候首先是 "#" == "#" ，之後遇到了 "^"和另一個字符比較，也就是到了邊界，才終止循環的。而 P [ i ] 並沒有遇到邊界，所以我們可以繼續通過中心擴展法一步一步向兩邊擴展就行了。
C 和 R 的更新
既然知道如何計算長度數組了，那最關鍵的 C 和 R 到底什麼時候需要更新呢？
i + P [ i ] > R時，也就是當求出的 P [ i ] 的右邊界大於當前的 R 時，我們就需要更新 C 和 R 為當前的迴文串了。因為我們必須保證 i 在 R 裡面，所以一旦有更右邊的 R 就要更新 R。
最終寫法
假設我們要寫一個方法，傳入參數是原字符串s，返回值是各個字符對應的最長迴文子串長度數組，那麼具體方法就是：
<code> public int[] calSubstrings(String s) {
if (s.length() == 0) {
return new int[0];
}
// 存放新的內容
char[] content = new char[s.length() * 2 + 3];
// 開頭用^
content[0] = '^';
// s中的每一個字符要用#包圍
content[1] = '#';
for (int i = 0; i < s.length(); i++) {
content[i * 2 + 2] = s.charAt(i);
content[i * 2 + 3] = '#';
}
// 結尾用$
content[content.length - 1] = '$';
// 當前的迴文串中心下標
int center = 0;
// 當前的迴文串右邊界
int right = 0;
// 存儲以每一個位置為中心，所能獲得的最長迴文子串的長度
int[] maxLength = new int[content.length];
// 首尾兩個字符沒有必要計算
for (int index = 1; index < content.length - 1; index++) {
// 如果當前求解的位置，在右邊界以內
if (index < right) {
// 則其最長迴文子串的長度，至少為：
maxLength[index] = Math.min(
// 對稱center的位置上的
maxLength[center * 2 - index],
// 或者當前位置到右邊界的距離
right - index
);
}
// 正常求解，向左右擴展
while (content[index + (maxLength[index] + 1)] ==
content[index - (maxLength[index] + 1)]) {
maxLength[index]++;
}
// 如果當前index對應的右邊界，比現有的right大
if (index + maxLength[index] > right) {
// 更新右邊界和中心
right = index + maxLength[index];
center = index;
}
}
// 最終的結果
int[] result = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
result[i] = maxLength[i * 2 + 2];
}
return result;
}
/<code>總結
以上就是我關於馬拉車算法的理解，用來解決最長迴文子串的問題，簡直就是一把利器。
有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
閱讀更多 健程之道 的文章
