【字符串处理系列】最长回文子串

这是一道非常经典的字符串处理问题，回文是指该字符串是对称的，如abcdcba, aabbaa

该问题最朴素的解法是找到所有子串，判断是不是回文并找出最长的回文子串，代码很简单，这里就不写了；

第二种解法是中心点法，即以某个点为中心，用两个索引分别往前和往后走，找出其回文，这里需要注意回文是奇数个字符还是偶数个字符，即要处理两种情况；

第三种解法是最有效的解法，时间复杂度比以上两种方法都低O(N)，该方法被称为Manacher算法，下面介绍该算法的思路：

       首先该算法采用了一个非常巧妙的方式将所有字符串的长度转换成奇数，即通过在字符串前面、字符串后面及各个字符之间添加一个特殊字符（如‘#’，‘$’），以字符串abcdedcbf为例，处理后的字符串s = "#a#b#b#d#e#d#b#b#f#";

       然后，建立一个辅助数组p，p中元素p[i]存储的是以s[i]为中心的回文半径，如下所示：

s   #  a  #  b  #  b  #  d  #  e  #  d  #  b  #  b  #  f  #

p  1   2  1  2  3  2  1  2  1  8  1  2  1  2  3  2  1  2  1

       这个算法的关键点在于p[i]的计算，p[i]是通过两个辅助变量id，mx来求解的，mx代表能到达最右边的回文的结尾，id代表该回文的中心点；当mx > i 时，则p[i] = min{ mx-i , p[2*id - i] }；这样可能比较难理解，我们用图表示出这两种情况会比较容易理解，看明白图后就会发现很简单：

2*id - i是i关于id的对称点，由于mx > i，所以i到mx之间的字符，mx的对称点到j之间的字符对称，如果以s[j]为中心的回文还没延伸到mx的对称点，因为i和j对称，所以以s[i]为中心的回文长度就等于p[j]，即p[2*id-i]；

当mx-i < p[j]时，此时我们可以先将p[i]指定为mx-i，然后再判断s[mx]之后的字符是否与前面的字符对称，该判断过程与另一种情况相同，即mx <= i时，此时也需要一个个字符判断；

该算法的代码如下：

public String longestPalindrome(String s) {
        if(s == null || s.length() == 0)
            return "";
        StringBuilder sb = new StringBuilder("#");
        for(int i = 0; i < s.length(); i++){
            sb.append(s.charAt(i)).append('#');
        }
        String str = sb.toString();
        int[] p = new int[str.length()];
        int id = -1;
        int mx = 0;
        int max = 0;
        for(int i = 0; i < str.length(); i++){
            if(i < mx){
                p[i] = Math.min(mx-i, p[2*id-i]);
            }else{
                p[i] = 1;
            }
            while(i+p[i] < str.length() && i-p[i] >= 0 && str.charAt(i+p[i]) == str.charAt(i-p[i]))
                p[i]++;
            if(i+p[i] > mx){
                id = i;
                mx = i+p[i];
            }
            if(p[i]  > p[max]){
                max = i;
            }
        }
        StringBuilder result = new StringBuilder();
        for(int i = max-p[max]+1; i <= max+p[max]-1; i++){
            if(str.charAt(i) != '#')
                result.append(str.charAt(i));
        }
        return result.toString();
    }
           

详见LeetCode：https://oj.leetcode.com/problems/longest-palindromic-substring/