问题

求字符串的最长回文子串

例如："aabbccbb"的最长回文子串是"bbccdd"

大家可能有各种思路去求解这个问题，今天介绍一个比较快的的算法——Manacher算法

算法简介

点击这里

算法分析

以"aabbccbb"为列，介绍一下Manacher算法是如何工作的。

算法的大致思路就是根据回文对称的特点，遍历字符串并以每个字符为中心向两边查找，并记录回文的半径长度，按照正常的思路，会出现两种情况偶回文和奇回文，例如"bbccbb"就是个偶回文，比较难处理。

所以这个叫Manacher的人想了一种办法，对字符串做以下处理

image

P数组就是记录回文子串的半径长度

这样就解决了偶回文和奇回文的问题

接下来就是重头戏，算法的魅力也就在此，Manacher算法充分利用回文的特点，它定义了两个变量：mx和id：

                id：是已知的最长回文子串的中心坐标

                mx：以id为中心的最长回文子串的右边界

这两个变量干嘛用呢，看图：

image

如图所示，n是i关于id对称的对称点，因为之前对回文n的半径长度有了计算，我们可以借助这个已知信息减少我们的计算量，根据回文的特点，可以得出P[i]=P[n]，当然这是个特殊情况，因为回文n在回文id的边界内

当回文n的左边界超过mx'时候，即n-p[n]<mx'，我们依然可以利用回文n的半径信息，因为回文n在回文id边界内的部分依然是回文（还是回文的特点），此时的P[n]=n-mx'，即P[n]=mx-i

所以P[i]=Min(P[n],mx-i);

代码实现

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);
      }
}