2018-06-16

Manacher算法求解最长回文子串

一、背景

最近在LintCode上面刷题时遇到了一个求解最长回文子串的问题，这个题目可以使用暴力的方式去进行求解，但算法的时间复杂度至少就是O(n^2)级别了，后面看讨论区时发现了一个比较有意思的算法，也就是今天的主题－－Manacher算法，用这个算法可以只需要O(n)级别的时间复杂度，花时间去学习了一下，感觉确实是挺好的一种思路，这里就来记录一下。

二、算法过程

1.简介

Manacher算法是通过求解一个中心点，在距离这个点R长度以内都是关于这个点左右对称的，也就是说这个长度为2R的字符串是一个回文串，最后再比较大小，求出最大的长度2R及其中心点，最后就得出了题解，并且整个过程就扫描整个字符串一遍。这里也可以看出，因为要求回文子串的中心点，这个中心点也是唯一的，所以它只能处理字符串是奇数位的情况。因此我们第一步就是把字符串长度变为奇数，这里就要使用一个非常巧妙的方式，把字符串中每个字符使用一个其它字符号包围起来，，这里以“＃”号为例，可以想象一下，要把每个字符都使用’’#’’号包裹，那么需要的#号总是要比原来的字符串长度多一位，才能保证每个字符都能被插入到#与#中间，简单举个例子

1 2	aa -> #a#a# aaa -> #a#a#a#

可以看到不管原来的字符串长度是什么，奇数加偶数结果肯定是奇数的，进行这一步处理后，就可以开始求最长回文子串的半径R了。

2.求解最长回文子串半径

这里可以先借助两个变量center、right分别记录回文子串对应的中心点和右端点，看看下图，

其实这里直接可以知道right就是2xcenter-i（也就是i关于center的对称点），既然是对称点，那么当端点right>i时，端点i需要进行计算回文子串R，但它的对称点有可能也进行过计算，所以可以无需从头开始匹配，因为这些点都包含在一个已经进行过匹配的父回文串中，所以这里可以直接取right-i和它的对称点回文子串半径长度较小的，用来保证绝对进行过计算的回文子串的部分;反之，就只能从1个长度开始匹配了，就是下面的这行代码，这里可能没如果还不理解的可以看看末尾的参考链接，这里我就不去画图了

1	r[i]=right>i?(Math.min(r[2*center-i], right-i)):1;

这里借助一个辅助的数组r[]来记录回文子串的半径R，r[i]表示的是以i为中心点的回文字符串的半径长度(初始情况下为1)，知道r[i]后，就可以继续把索引向左右两边扩充，也就是看i+r[i]与i-r[i]左右端点的位置所对应的字符是否相等，相等的话就把回文半径r[i]继续扩充，直到不相等为止。进行这一轮扩充后，就去看看之前的右端点right是否小于回文子串扩充后的右端点i+r[i],小于就直接更新右端点和中心点，不小于就说明当前回文子串还是在当前right端点的内部。

3.全部代码

public class Test200 {
    public String longestPalindrome(String s) {
        // write your code here
        StringBuilder builder = new StringBuilder();
       // 防止左端点越界
        builder.append("&#");
        char[] c = s.toCharArray();
        for (int i=0;i < c.length;i++) {
            builder.append(c[i]+"#");
        }
        String newStr = builder.toString();
        c = newStr.toCharArray();
        // 回文半径
        int[] r = new int[newStr.length()];
        // 回文子串最大右端点、中心点
        int right=0, center=0;
        // 最大回文半径、最大中心点
        int maxR=0, maxC=0;
        for (int i=1;i < c.length;i++) {
　　　// 以i为中心点的回文半径，可以重复利用以及匹配过对称点的半径
            r[i]=right>i?(Math.min(r[2*center-i], right-i)):1;
            while (i+r[i]<c.length && c[i+r[i]]==c[i-r[i]]) {
                ++r[i];
            }
            // 更新右端点和中心点
            if (right < i+r[i]) {
                right = i+r[i];
                center = i;
            }
            // 更新最大半径和最大中心点
            if (maxR < r[i]) {
                maxR = r[i];
                maxC = i;
            }
        }
        // 计算在原字符串中的起始点
        int start = (maxC-maxR)/2;
        return s.substring(start, start+maxR-1);
    }
    public static void main(String[] args) {
        String s = "aa";
        Test200 test = new Test200();
        System.out.println(test.longestPalindrome(s));
    }
}