算法笔记之Manacher算法

问题引入

问题描述：最长回文子串问题
	给定一个字符串，求它的最长回文子串长度。
示例：
	s = abbabbac  最长回文子串为：abbabba

解法一：中心扩展法

任何一个回文串一定关于某个中心字符对称的，偶数长度的字符串对称中心是长度为2的字符，例如aabbaa中的对称中心是bb，奇数长度的字符串对称中心是长度为1的字符，例如acbca的对称中心是b。根据这个特性，针对任何一个字符串，可以对所有可能的对称中心向外拓展，例如：aabbaa的长度为1的对称中心a,a,b,b,a,a,长度为2的对称中心aa,bb,aa。当拓展是，只要保证最外层两个字符相等，那么就是一个回文串。对于长度为n的字符串，对称中心有2n-1个，每个对称中心扩展比较的复杂度是On,所以此算法的时间复杂度是O(n^2)。

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

解法二：Manacher算法

中心扩展法虽然很直观，但是时间复杂度是O(n^2),这对于长字符串是不可以接受的。于是，就要介绍文章的主角：Manacher(马拉车)算法。马拉车算法通过巧妙的手法，实现了On的复杂度，鬼斧神工。

解法一存在着部分缺陷：

回文串长度的奇偶性带来了两种不同的对称中心，需要不同的处理。

在进行中心扩展时，做了很多重复的访问。

1
2
3

例如： S = "ababa"
	  i =  01234
当：i=1,i=2时，子串aba被访问了两次。

下面来看Manacher算法的改进：

（1）解决长度奇偶性带来的对称中心问题

Manacher算法对字符串进行了预处理，在所有字符中间插入字符串中未出现过得字符。通过这种方式，所有的回文子串的长度都是奇数长度的。可证明，一定不存在偶数的回文子串。

1 2	aba => #a#b#a# abba => #a#b#b#a#

（2）解决中心扩展出现的重复检查问题

当进行遍历的途中，可以根据以下分析：

index: 0 1 2 3 4 5 6 7 8 9
假设当前的扩散中心是 6,而且0-5已经检查完毕,0-5的为中心的最大回文串长度已经确定。
此时，如果 以4为中心的最大回文串是: 12345678;
	 那么 6的回文子串在<8的范围内理应和 6关于4对称的2中心所构成的部分子串是相同的。
通过以上的推论：
	1. 当检查某个中心是，尽可能找到之前对称的部分子串，减少枚举长度。
	2. 为了然能找到的子串尽可能的大，需要维护一个所有中心最大回文子串所能到达的最右端点。

为了更好的实现算法，需要引入以下概念：

回文半径：一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径
例如：
	S: # a # b # a #
	p: 1 2 1 4 1 2 1
  p-1: 0 1 0 3 0 1 0
    i: 0 1 2 3 4 5 6
而且，p-1的最大值，恰好就是原字符串回文子串的最大长度。

根据上述的两点：求最长回文子串，那就是求这个回文半径数组；而且，当我们想要求i位置的p[i]时，按照如上分析，可以利用p[0-i-1]的数据减少运算。

public static int manacher(String s){
    String sMan = manacherPrepare(s);
    int[] p = new int[sMan.length()];
    int maxRight = 0,pos = 0,maxLen = 0;
    for(int i=0;i<sMan.length();i++){
        p[i] = i<maxRight ? Math.min(p[2*pos-i],maxRight-i):1;
        while (i-p[i]>=0 && i+p[i]<sMan.length() && sMan.charAt(i-p[i])==sMan.charAt(i+p[i])){
            p[i]++;
        }
        if(p[i]+i-1 > maxRight){
            maxRight = p[i] + i -1;
            pos = i;
        }
        maxLen = Math.max(maxLen,p[i]);
    }
    return maxLen-1;
}
public static String manacherPrepare(String s){
    StringBuilder sb = new StringBuilder();
    for(char c:s.toCharArray()){
        sb.append('#');
        sb.append(c);
    }
    sb.append('#');
    return sb.toString();
}