O(n) 時間內尋找 “迴文子串”
在leetcode上看到一種O(n)時間內尋找“迴文子串”的演算法，雖然簡單，但是思路很棒，寫文章記錄下。
原題：
連結：https://leetcode.com/problems/longest-palindromic-substring/
一、一般思路：“中間開花”
遍歷所有字元，對於每個字元以其為中心往兩邊擴充套件，計算半徑。記錄下最長半徑的解即可。
這種方式的時間複雜度是O(n^2)。在求解過程中，基數的迴文子串與偶數的迴文子串是不一樣的。比如最長迴文子串為aba，對稱中心就是b，如果最長迴文子串為abba，則對稱中心應該為兩個b之間，為了解決這個問題，可以在每個字元兩邊加上一個符號，具體什麼符號（是字串裡面的符號也行）對結果沒有影響，比如加上“#”，則上述的兩個序列變成了#a#b#a#和#a#b#b#a#，求出的長度分別為6和9，再除以2就可以得到最後的結果3和4。這種方式的時間複雜度太高，下面介紹時間複雜度為O(n)的Manacher演算法。
簡例：
while(i+radius[i] < charArr.length && i - radius[i] > -1){
if(charArr[i-radius[i]] == charArr[i+radius[i]]){
radius[i]++;
}else{
break;
}
}
二、Manacher演算法中的基礎概念
正式計算前，先對字串做奇數長度處理。原字串" babad" ，處理後"# b#a#b#a#d# ”
(1)迴文半徑陣列p
也就是以該點為中心，形成的最長迴文串的半徑是多少，很簡單，得出p = [1,2,1,4,1,4,1,2,1,2,1]
(2)最右迴文右邊界R
一個位置最右迴文右邊界指的是這個位置及之前的位置的迴文子串，所到達的最右邊的地方。比如對於字串 # b#a#b#a#d#，遍歷到4（p.s. 本文下邊都以0開始）這個位置的時，R=6。原因也很簡單， # b#a#b#是4之前的中心點所能產生的迴文串最右邊界值。
三、Manacher演算法的流程
首先大的方面分為兩種情況：
第一種情況：i > R,下一個要移動的位置在最右迴文右邊界R的右邊。
比如在最開始時，R=-1,p的下一個移動的位置為p=0，p=0在R=-1的右邊；p=0時，此時的R=0，p的下一個移動位置為p=1，也在R=0的右邊。
在這種情況下，採用普遍的解法，將移動的位置為對稱中心，向兩邊擴，同時更新迴文半徑陣列，最右迴文右邊界R和最右迴文右邊界的對稱中心C。
第二種情況：i<=R,下一個要移動的位置就是最右迴文右邊界R或是在R的左邊
在這種情況下又分為三種：
1、下一個要移動的位置p1不在最右迴文右邊界R右邊，且cL<pL。
p2是p1以C為對稱中心的對稱點；
pL是以p2為對稱中心的迴文子串的左邊界;
cL是以C為對稱中心的迴文子串的左邊界。
這種情況下p1的迴文半徑就是p2的迴文半徑radius[p2]。
p1<=R且cL<pL
2、下一個要移動的位置票p1不在最右迴文右邊界R的右邊，且cL>pL。
p2是p1以C為對稱中心的對稱點；
pL是以p2為對稱中心的迴文子串的左邊界；
cL是以C為對稱中心的迴文子串的左邊界。
這種情況下p1的迴文半徑就是p1到R的距離R-p1+1。
p1<=R且cL>pL
3、下一個要移動的位置票p1不在最右迴文右邊界R的右邊，且cL=pL；
p2是p1以C為對稱中心的對稱點；
pL是以p2為對稱中心的迴文子串的左邊界；
cL是以C為對稱中心的迴文子串的左邊界。
這種情況下p1的迴文半徑就還要繼續往外擴，但是隻需要從R之後往外擴就可以了，擴了之後更新R和C。
p1<=R且cL==pL
四、Manacher時間複雜度分析
從上面的分析中，可以看出，第二種情況的1，2的求某個位置的迴文半徑的時間複雜度是O(1)，對於第一種情況和第二種情況的3，R是不斷的向外擴的，不會往回退，而且R之內的位置是不是進行判斷的。所以對整個字串而且，R的移動是從字串的起點移動到終點，時間複雜度是O(n),所以整個manacher的時間複雜度是O(n)。
五、答案
runTime：13ms
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int max = -1;
int R = -1;
int c = -1;
int begin = -1;
int end = -1;
char[] data = transOddStr(s);
int length = data.length;
int[] p = new int[length];
for (int i = 0; i < length; i++) {
p[i] = i < R ? Math.min(p[2 * c - i], R - i + 1) : 1;
while (i - p[i] > -1 && i + p[i] < length) {
if (data[i - p[i]] == data[i + p[i]]) {
p[i]++;
} else {
break;
}
}
if (i + p[i] - 1 >= R) {
R = i + p[i] - 1;
c = i;
}
if(p[i] > max) {
max = p[i];
begin = i - p[i] + 1;
end = i + p[i] - 1;
}
}
return remove(new String(data).substring(begin, end+1));
}
private char[] transOddStr(String s) {
StringBuffer newStr = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
newStr.append("#").append(s.charAt(i));
}
newStr.append("#");
return newStr.toString().toCharArray();
}
private String remove(String s) {
StringBuffer newStr = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) != '#') {
newStr.append(s.charAt(i));
}
}
return newStr.toString();
}
}