O(n) 时间内寻找 “回文子串”

在leetcode上看到一种O(n)时间内寻找“回文子串”的算法，虽然简单，但是思路很棒，写文章记录下。

原题：

链接：https://leetcode.com/problems/longest-palindromic-substring/

一、一般思路：“中间开花”

遍历所有字符，对于每个字符以其为中心往两边扩展，计算半径。记录下最长半径的解即可。

这种方式的时间复杂度是O(n^2)。在求解过程中，基数的回文子串与偶数的回文子串是不一样的。比如最长回文子串为aba，对称中心就是b，如果最长回文子串为abba，则对称中心应该为两个b之间，为了解决这个问题，可以在每个字符两边加上一个符号，具体什么符号（是字符串里面的符号也行）对结果没有影响，比如加上“#”，则上述的两个序列变成了#a#b#a#和#a#b#b#a#，求出的长度分别为6和9，再除以2就可以得到最后的结果3和4。这种方式的时间复杂度太高，下面介绍时间复杂度为O(n)的Manacher算法。

简例：

while(i+radius[i] < charArr.length && i - radius[i] > -1){
    if(charArr[i-radius[i]] == charArr[i+radius[i]]){
        radius[i]++;
    }else{
        break;
    }
}

二、Manacher算法中的基础概念

正式计算前，先对字符串做奇数长度处理。原字符串" babad" ，处理后"# b#a#b#a#d# ”

(1)回文半径数组p

也就是以该点为中心，形成的最长回文串的半径是多少，很简单，得出p = [1,2,1,4,1,4,1,2,1,2,1]

(2)最右回文右边界R

一个位置最右回文右边界指的是这个位置及之前的位置的回文子串，所到达的最右边的地方。比如对于字符串 # b#a#b#a#d#，遍历到4（p.s. 本文下边都以0开始）这个位置的时，R=6。原因也很简单， # b#a#b#是4之前的中心点所能产生的回文串最右边界值。

三、Manacher算法的流程

首先大的方面分为两种情况：

第一种情况：i > R,下一个要移动的位置在最右回文右边界R的右边。

比如在最开始时，R=-1,p的下一个移动的位置为p=0，p=0在R=-1的右边；p=0时，此时的R=0，p的下一个移动位置为p=1，也在R=0的右边。

在这种情况下，采用普遍的解法，将移动的位置为对称中心，向两边扩，同时更新回文半径数组，最右回文右边界R和最右回文右边界的对称中心C。

第二种情况：i<=R,下一个要移动的位置就是最右回文右边界R或是在R的左边

在这种情况下又分为三种：

1、下一个要移动的位置p1不在最右回文右边界R右边，且cL<pL。

p2是p1以C为对称中心的对称点；

pL是以p2为对称中心的回文子串的左边界;

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就是p2的回文半径radius[p2]。

p1<=R且cL<pL

2、下一个要移动的位置票p1不在最右回文右边界R的右边，且cL>pL。

p2是p1以C为对称中心的对称点；

pL是以p2为对称中心的回文子串的左边界；

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就是p1到R的距离R-p1+1。

p1<=R且cL>pL

3、下一个要移动的位置票p1不在最右回文右边界R的右边，且cL=pL；

p2是p1以C为对称中心的对称点；

pL是以p2为对称中心的回文子串的左边界；

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就还要继续往外扩，但是只需要从R之后往外扩就可以了，扩了之后更新R和C。

p1<=R且cL==pL

四、Manacher时间复杂度分析

从上面的分析中，可以看出，第二种情况的1，2的求某个位置的回文半径的时间复杂度是O(1)，对于第一种情况和第二种情况的3，R是不断的向外扩的，不会往回退，而且R之内的位置是不是进行判断的。所以对整个字符串而且，R的移动是从字符串的起点移动到终点，时间复杂度是O(n),所以整个manacher的时间复杂度是O(n)。

五、答案

runTime：13ms

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int max = -1;
        int R = -1;
        int c = -1;
        int begin = -1;
        int end = -1;
        char[] data = transOddStr(s);
        int length = data.length;
        int[] p = new int[length];
        for (int i = 0; i < length; i++) {

            p[i] = i < R ? Math.min(p[2 * c - i], R - i + 1) : 1;
            while (i - p[i] > -1 && i + p[i] < length) {
                if (data[i - p[i]] == data[i + p[i]]) {
                    p[i]++;
                } else {
                    break;
                }
            }

            if (i + p[i] - 1 >= R) {
                R = i + p[i] - 1;
                c = i;
            }
            if(p[i] > max) {
                max = p[i];
                begin = i - p[i] + 1;
                end = i + p[i] - 1;
            }
        }

        return remove(new String(data).substring(begin, end+1));
    }

    private char[] transOddStr(String s) {
        StringBuffer newStr = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            newStr.append("#").append(s.charAt(i));
        }
        newStr.append("#");
        return newStr.toString().toCharArray();
    }

    private String remove(String s) {
        StringBuffer newStr = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) != '#') {
                newStr.append(s.charAt(i));
            }
        }
        return newStr.toString();
    }
}