問題
求字符串的最長回文子串
例如："aabbccbb"的最長回文子串是"bbccdd"
大家可能有各種思路去求解這個問題或辖，今天介紹一個比較快的的算法——Manacher算法
算法簡介
算法分析
以"aabbccbb"為列卤唉，介紹一下Manacher算法是如何工作的。
算法的大致思路就是根據(jù)回文對稱的特點(diǎn)威恼，遍歷字符串并以每個字符為中心向兩邊查找，并記錄回文的半徑長度绵载，按照正常的思路饲梭，會出現(xiàn)兩種情況偶回文和奇回文，例如"bbccbb"就是個偶回文早歇，比較難處理倾芝。
所以這個叫Manacher的人想了一種辦法，對字符串做以下處理
image
P數(shù)組就是記錄回文子串的半徑長度
這樣就解決了偶回文和奇回文的問題
接下來就是重頭戲缺前，算法的魅力也就在此蛀醉，Manacher算法充分利用回文的特點(diǎn)，它定義了兩個變量：mx和id：
id：是已知的最長回文子串的中心坐標(biāo)
mx：以id為中心的最長回文子串的右邊界
這兩個變量干嘛用呢衅码，看圖：
image
如圖所示拯刁，n是i關(guān)于id對稱的對稱點(diǎn)，因?yàn)橹皩匚膎的半徑長度有了計算逝段，我們可以借助這個已知信息減少我們的計算量垛玻，根據(jù)回文的特點(diǎn)割捅，可以得出P[i]=P[n]，當(dāng)然這是個特殊情況帚桩，因?yàn)榛匚膎在回文id的邊界內(nèi)
當(dāng)回文n的左邊界超過mx'時候亿驾，即n-p[n]<mx'，我們依然可以利用回文n的半徑信息账嚎，因?yàn)榛匚膎在回文id邊界內(nèi)的部分依然是回文（還是回文的特點(diǎn)）莫瞬，此時的P[n]=n-mx'，即P[n]=mx-i
所以P[i]=Min(P[n],mx-i);
代碼實(shí)現(xiàn)
public class Manacher {
private String sourStr;
private StringBuilder destStr;
private int[] p;
public Manacher(String sour){
this.sourStr=sour;
this.destStr=new StringBuilder();
initStr();
}
private void initStr(){
int len=0;
destStr.append('#');
for (int i=0;i<sourStr.length();i++){
destStr.append(sourStr.charAt(i));
destStr.append('#');
}
len=destStr.length();
p=new int[len];
}
public String method(){
int len=destStr.length();
int mx=0;
int id=1;
int maxLen=-1;
int result=-1;
for (int i=1;i<len;i++){
if(i<mx) p[i]=Math.min(p[2*id-i],mx-i);
else p[i]=1;
while (((i-p[i]>=0 && i+p[i]<len)) && destStr.charAt(i-p[i])==destStr.charAt(i+p[i]))
p[i]++;
if(mx<i+p[i]){
id=i;
mx=i+p[i];
}
if(maxLen<p[i]) {
maxLen= p[i];
result= i;
}
}
return destStr.substring(result-maxLen+1,result+maxLen);
}
}
