題目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
樣例
-
Example 1
Input: "babad" Output: "bab" Note: "aba" is also a valid answer. -
Example 2
Input: "cbbd" Output: "bb"
思想
這里來說一下O(n)來解決最長回文串的問題，即Manacher算法
那么首先需要說一個O(n2)的方法饶囚，然后才能體會O(n)的方法的真正巧妙的地方在哪里走哺。O(n2)的方法是枚舉一個中心點i，然后向左右兩邊查找肺樟，直到發(fā)現(xiàn)Str[i-k]與Str[i+k]不相等了，或者是越界了，再開始下一次中心點的枚舉关筒。然后對于"baab"這樣沒有中心點的對稱回文描孟，又要用相同的方法再做一次（中心點變成兩個）驶睦。
大家就會發(fā)現(xiàn)如果遇到了像"cccccc"砰左，這樣多次重復(fù)的串，那么一個位置就會被重復(fù)訪問多次场航，這就是它很慢的根本原因缠导，并且奇偶分別解決的話也非常的麻煩。那么我們就需要想辦法來規(guī)避掉這兩個問題溉痢。對于搜索狀態(tài)的重復(fù)性的解決方案一般就是利用DP（對于無后效性的問題）僻造。那么我們就使用DP的思想再來思考一下這個問題，就會發(fā)現(xiàn)有一些狀態(tài)是可以被繼承的孩饼。因為這是回文串髓削，那么就會出現(xiàn)a與b關(guān)于c成鏡像的情況，進一步在以c為中心的回文串當(dāng)中镀娶，以a為中心的回文串和以b為中心的回文串一定是相同的立膛。（這里沒看懂不要緊，后面會具體畫圖分析）
那么我們就利用這個特性梯码，就能解決掉重復(fù)訪問的問題宝泵。對于奇偶的問題，我們就可以使用插入'#'號的方法來規(guī)避掉轩娶。（這個辦法真是太巧妙了）
baab => #b#a#a#b#
bacab => #b#a#c#a#b#
這樣就把奇偶的回文串全部轉(zhuǎn)化成了奇數(shù)的回文串儿奶。
好了，那下面進入正題罢坝，怎么解決掉重復(fù)訪問的問題廓握？
- 我們可以先證明一個命題：RL[i]表示在變形字符串中以i為中心的回文串的半徑，RL[i]-1是在原字符串中以Str[i]為中心的最長回文串的長度
例如：bacab => #b#a#c#a#b#
原字符串的長度為5嘁酿，變形后的長度為11隙券。
RL[6] = 6，即在變形串中以c為中心的最長回文串的半徑為6闹司。
那么整個回文串的長度應(yīng)為L = 2 * RL[6] -1娱仔。
因為該回文串首尾必定為'#'，所以隨便去掉首部或者尾部的'#'后游桩，該回文串為原回文串長度的2倍牲迫。
所以原回文串長度L` = [2 * RL[6] - 2] / 2 = RL[6] - 1
- 那么我們的任務(wù)也就是快速計算RL數(shù)組了，這里就需要用到前面提到的思想借卧。首先我們來設(shè)幾個值盹憎，maxRight（現(xiàn)在能觸及到的最右邊的位置），pos（觸及到最右邊位置時回文中心的index）铐刘，i（計算RL數(shù)組的枚舉變量）陪每。
-
i <= maxRight :
- 這時我們觀察上圖可以發(fā)現(xiàn)在兩個紅格子之間的所有格子都是關(guān)于pos對稱的，也就是i也有關(guān)于pos對稱的點。那我們可以計算出i關(guān)于pos的對稱點j = 2 * pos - i檩禾。
- 這時候又要分為兩種情況挂签，第一種是pos - j + 1> RL[j]，即j的回文串半徑?jīng)]有超過MaxRight的鏡像盼产。這時就很簡單了饵婆，因為都是關(guān)于pos對稱的，那么i的回文串和j的回文串也是對稱的戏售。RL[i] = RL[j]
-
那第二種情況侨核，j的回文串半徑超過了MaxRight的鏡像。那么i只能繼承j在這個鏡像區(qū)域的部分蜈项，并且繼承之后需要繼續(xù)向兩邊擴展芹关。這里需要注意因為需要繼續(xù)擴展续挟，那么就很有可能會刷新maxRight值和pos值紧卒。
- 這時我們觀察上圖可以發(fā)現(xiàn)在兩個紅格子之間的所有格子都是關(guān)于pos對稱的，也就是i也有關(guān)于pos對稱的點。那我們可以計算出i關(guān)于pos的對稱點j = 2 * pos - i檩禾。
-
i > maxRight :
- 這種情況就很簡單了，因為i已經(jīng)超過了maxRight诗祸，那么就不能繼承鏡像的任何東西跑芳。就只能自己向兩邊擴展了。這里也可能會刷新maxRight的pos的值直颅。
-
i <= maxRight :
以上圖片均來自網(wǎng)上博客
代碼
public int extendIndex(char[] charArr, int i, int l, int r) {
while (l - 1 >= 0 && r + 1 < charArr.length) {
if (charArr[l - 1] == charArr[r + 1]) {
l --;
r ++;
} else {
break;
}
}
return (i - l + 1);
}
public String longestPalindrome(String s) {
char[] _s = s.toCharArray();
char[] charArr = new char[_s.length * 2 + 1];
int[] f = new int[charArr.length];
int id = -1, maxRight = -1, ansId = 0, max = -1;
charArr[0] = '#';
for (int i = 1; i <= _s.length; i++) {
charArr[i * 2 - 1] = _s[(i - 1)];
charArr[i * 2] = '#';
}
for (int i = 0; i < charArr.length; i++) {
if (i > maxRight) {
f[i] = extendIndex(charArr, i, i, i);
} else {
// i 關(guān)于id的鏡像
int j = 2 * id - i;
if (i + f[j] - 1 >= maxRight) {
f[i] = extendIndex(charArr, i, 2 * i - maxRight, maxRight);
} else {
f[i] = f[j];
}
}
if (i + f[i] - 1 > maxRight) {
maxRight = i + f[i] - 1;
id = i;
}
if (f[i] > max) {
max = f[i];
ansId = i;
}
}
char[] res = new char[(max - 1)];
int index = 0;
for (int i = -max + 1; i < max; i++) {
if (charArr[ansId + i] != '#') {
res[index] = charArr[ansId + i];
index ++;
}
}
String resStr = String.valueOf(res);
return resStr;
}
代碼不夠精簡博个，后續(xù)會更新一個精簡版
復(fù)雜度分析
以上進行了算法的分析，那最后分析一下這種算法的復(fù)雜度和在O(n^2)算法的基礎(chǔ)上的提高功偿。
- 關(guān)于Manacher算法的時間復(fù)雜度分析具體可以參見：知乎-如何證明Manacher算法的時間復(fù)雜度是O(n)?
- 我僅僅簡單說說我的想法盆佣，在每一次循環(huán)當(dāng)中會涉及到一個問題，maxRight會不會被向右推動械荷，如果maxRight不被向右推動共耍，那么這次循環(huán)O(1)能夠完成。如果maxRight被向右推動吨瞎，理論上是O(n)才能完成痹兜，但是因為能進行繼承，所以這個值遠小于n颤诀，并且當(dāng)maxRight達到n時字旭，整個算法結(jié)束。所以n會被分散在每次推動的復(fù)雜度中的崖叫。
- 現(xiàn)在再回過頭來看整個算法遗淳，主要是在O(n^2)算法的基礎(chǔ)之上利用了繼承前面的計算結(jié)果來減少一個元素的多次訪問問題。并且很巧妙的利用了回文串的鏡像原理心傀。
