Manacher算法，又叫“馬拉車”算法，可以在時(shí)間復(fù)雜度為O(n)的情況下求解一個(gè)字符串的最長(zhǎng)回文子串長(zhǎng)度的問題。
一、回文子串的一般解法
比較簡(jiǎn)單的思路是將字符串的每一個(gè)字符作為回文子串的中心對(duì)稱點(diǎn)，每次保存前面求得的回文子串的最大值，最后得到的就是最長(zhǎng)的回文子串的長(zhǎng)度，這種方式的時(shí)間復(fù)雜度是O(n^2)。在求解過(guò)程中，基數(shù)的回文子串與偶數(shù)的回文子串是不一樣的。比如最長(zhǎng)回文子串為aba，對(duì)稱中心就是b，如果最長(zhǎng)回文子串為abba，則對(duì)稱中心應(yīng)該為兩個(gè)b之間，為了解決這個(gè)問題，可以在每個(gè)字符兩邊加上一個(gè)符號(hào)，具體什么符號(hào)（是字符串里面的符號(hào)也行）對(duì)結(jié)果沒有影響，比如加上“#”，則上述的兩個(gè)序列變成了#a#b#a#和#a#b#b#a#，求出的長(zhǎng)度分別為6和9，再除以2就可以得到最后的結(jié)果3和4。這種方式的時(shí)間復(fù)雜度太高，下面介紹時(shí)間復(fù)雜度為O(n)的Manacher算法。
二、Manacher算法中的基礎(chǔ)概念
在進(jìn)行Manacher算法時(shí)，字符串都會(huì)進(jìn)行上面的進(jìn)入一個(gè)字符處理，比如輸入的字符為acbbcbds，用“#”字符處理之后的新字符串就是#a#c#b#b#c#b#d#s#。
1、回文半徑數(shù)組radius
回文半徑數(shù)組radius是用來(lái)記錄以每個(gè)位置的字符為回文中心求出的回文半徑長(zhǎng)度，如下圖所示，對(duì)于p1所指的位置radius[6]的回文半徑是5，每個(gè)位置的回文半徑組成的數(shù)組就是回文數(shù)組，所以#a#c#b#b#c#b#d#s#的回文半徑數(shù)組為[1, 2, 1, 2, 1, 2, 5, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1]。
2、最右回文右邊界R
一個(gè)位置最右回文右邊界指的是這個(gè)位置及之前的位置的回文子串，所到達(dá)的最右邊的地方。比如對(duì)于字符串#a#c#b#b#c#b#d#s#，求它的每個(gè)位置的過(guò)程如下：
最開始的時(shí)候R=-1，到p=0的位置，回文就是其本身，最右回文右邊界R=0;p=1時(shí)，有回文串#a#，R=2；p=2時(shí)，R=2;P=3時(shí)，R=6;p=4時(shí)，最右回文右邊界還是p=3時(shí)的右邊界，R=6,依次類推。
3、最右回文右邊界的對(duì)稱中心C
就是上面提到的最右回文右邊界的中心點(diǎn)C，如下圖，p=4時(shí)，R=6，C=3
三、Manacher算法的流程
首先大的方面分為兩種情況：
第一種情況：下一個(gè)要移動(dòng)的位置在最右回文右邊界R的右邊。
比如在最開始時(shí)，R=-1,p的下一個(gè)移動(dòng)的位置為p=0，p=0在R=-1的右邊；p=0時(shí)，此時(shí)的R=0，p的下一個(gè)移動(dòng)位置為p=1，也在R=0的右邊。
在這種情況下，采用普遍的解法，將移動(dòng)的位置為對(duì)稱中心，向兩邊擴(kuò)，同時(shí)更新回文半徑數(shù)組，最右回文右邊界R和最右回文右邊界的對(duì)稱中心C。
第二種情況：下一個(gè)要移動(dòng)的位置就是最右回文右邊界R或是在R的左邊
在這種情況下又分為三種：
1、下一個(gè)要移動(dòng)的位置p1不在最右回文右邊界R右邊，且cL<pL。
p2是p1以C為對(duì)稱中心的對(duì)稱點(diǎn)；
pL是以p2為對(duì)稱中心的回文子串的左邊界;
cL是以C為對(duì)稱中心的回文子串的左邊界。
這種情況下p1的回文半徑就是p2的回文半徑radius[p2]。
2、下一個(gè)要移動(dòng)的位置票p1不在最右回文右邊界R的右邊，且cL>pL。
p2是p1以C為對(duì)稱中心的對(duì)稱點(diǎn)；
pL是以p2為對(duì)稱中心的回文子串的左邊界；
cL是以C為對(duì)稱中心的回文子串的左邊界。
這種情況下p1的回文半徑就是p1到R的距離R-p1+1。
3、下一個(gè)要移動(dòng)的位置票p1不在最右回文右邊界R的右邊，且cL=pL；
p2是p1以C為對(duì)稱中心的對(duì)稱點(diǎn)；
pL是以p2為對(duì)稱中心的回文子串的左邊界；
cL是以C為對(duì)稱中心的回文子串的左邊界。
這種情況下p1的回文半徑就還要繼續(xù)往外擴(kuò)，但是只需要從R之后往外擴(kuò)就可以了，擴(kuò)了之后更新R和C。
四、Manacher時(shí)間復(fù)雜度分析
從上面的分析中，可以看出，第二種情況的1，2的求某個(gè)位置的回文半徑的時(shí)間復(fù)雜度是O(1)，對(duì)于第一種情況和第二種情況的3，R是不斷的向外擴(kuò)的，不會(huì)往回退，而且尋找回文半徑時(shí)，R之內(nèi)的位置是不是進(jìn)行判斷的，所以對(duì)整個(gè)字符串而且，R的移動(dòng)是從字符串的起點(diǎn)移動(dòng)到終點(diǎn)，時(shí)間復(fù)雜度是O(n),所以整個(gè)manacher的時(shí)間復(fù)雜度是O(n)。
五、Manacher的代碼實(shí)現(xiàn)
public static void main(String[] args) {
String str = "abcdcbafabcdck";
//String str = "acbbcbds";
System.out.println(manacher(str));
}
public static char[] manacherString(String str){
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
sb.append("#");
sb.append(str.charAt(i));
}
sb.append("#");
return sb.toString().toCharArray();
}
public static int manacher(String str){
if(str == null || str.length() < 1){
return 0;
}
char[] charArr = manacherString(str);
int[] radius = new int[charArr.length];
int R = -1;
int c = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < radius.length; i++) {
radius[i] = R > i ? Math.min(radius[2*c-i],R-i+1):1;
while(i+radius[i] < charArr.length && i - radius[i] > -1){
if(charArr[i-radius[i]] == charArr[i+radius[i]]){
radius[i]++;
}else{
break;
}
}
if(i + radius[i] > R){
R = i + radius[i]-1;
c = i;
}
max = Math.max(max,radius[i]);
}
return max-1;
}
