manacher算法

题目：Manacher 算法

算法简介：

Manacher算法是一个叫Manacher的人在1975年发明的， 这个方法最大的贡献是将回文字符串匹配的时间复杂度降低到了线性。

算法流程：

首先先解决字符串奇偶不一样的问题，我们在每两个字符的中间加入一个’#’(可以不是#，只要是字符串中原来没有出现过的字符就行)，之后为了使我们在遍历匹配字符的过程中，到达边界能够自动结束，所以我们在字符串的两头分别加入’^’和’$’（同理，也可以不是这两个字符，只要是原字符串中没有出现过的字符即可）。
原理：因为奇数个字符的“空隙”一定有偶数个，偶数个字符的“空隙”一定有奇数个，所以我们这么改变字符串之后，字符串一定会变成奇数字符串，这样就解决了奇偶字符串匹配不一样的问题。
之后，我们用一个数组P来保存，以当前字符为中心，能向两边扩展的长度，也就是回文半径,而回文半径正好是去掉’#’的原字符串的总长度。举个栗子🌰：

从上图中，可以看到P[6] = 5,也就是在P[6]这个位置，可以向两边扩展5个长度的字符串，组成回文字符串，即”#c#b#c#b#c#”,去掉所有’#’后，变成了”cbcbc”，他的长度正好是回文半径的长度5。
接下来，我们就可以求出原回文字符串开头位置字符的下标了，用P的下标i减去P[i]再除以2，这是因为，前面每个字符中间都有一个’#’所以前面的字符数和’#’数相等，所以我们用当前下标减去回文半径再除以二就得到了原回文字符串开头位置的下标了。
举个例子🌰：还是上面那个图，比如我们要求P[6]对应的回文字符串开头位置的下标，我们就用（6-5）/ 2 = 0，就说明开头位置的下标是0，所以我们得到的回文子字符串的下标就是[0，5-1] = [0,4]
接下来，就到了整个算法的关键所在了，就是求P[i]，求以每个字符为中心的回文半径，在这一步充分利用了回文字符串的对称性。
我们规定，用C表示回文字符串的中心，R表示回文半径，所以R=C+P[i]，C和R所对应的回文字符串是当前循环中最靠右的回文字符串。
我们用i表示当前正在求得回文字符串的中心位置的下标，i_mirror表示i关于C对称的下标。🌰：

我们现在要求P[i]，如果使用中心扩展法，我们就直接从i往两边扩展就行了，但是这样时间复杂度太高，我们可以利用回文字符串C的对称性，i关于C的对称点是i_mirror，P[i_mirror]= 3，所以P[i]也等于3。但是有三种情况会造成给P[i]直接赋值P[i_mirror]不正确，下面一一讨论。

1. P[i]+P[i_mirror]>R:
   
   当我们要求 P [ i ] 的时候，P [ mirror ] = 7，而此时 P [ i ] 并不等于 7，为什么呢，因为我们从 i 开始往后数 7 个，等于 22，已经超过了最右的 R，此时不能利用对称性了，但我们一定可以扩展到 R 的，所以 P [ i ] 至少等于 R - i = 20 - 15 = 5，会不会更大呢，我们只需要比较 T [ R+1 ] 和 T [ R+1 ]关于 i 的对称点就行了，就像中心扩展法一样一个个扩展。

2. P [ i_mirror ] 遇到了原字符串的左边界
   
   此时P [ i_mirror ] = 1，但是 P [ i ] 赋值成 1 是不正确的，出现这种情况的原因是 P [ i_mirror ] 在扩展的时候首先是 “#” == “#”，之后遇到了 “^” 和另一个字符比较，也就是到了边界，才终止循环的。而 P [ i ] 并没有遇到边界，所以我们可以继续通过中心扩展法一步一步向两边扩展就行了

3. i 等于了 R
   此时我们先把 P [ i ] 赋值为 0，然后通过中心扩展法一步一步扩展就行了。

   最后，我们考虑C和R的更新问题，我们一步一步求出P[i]之后，当求出的 P [ i ] 的右边界大于当前的 R 时，我们就需要更新 C 和 R 为当前的回文串了。因为我们必须保证 i 在 R 里面，所以一旦有更右边的 R 就要更新 R。

代码：

public String preProcess(String s) {
    int n = s.length();
    if (n == 0) {
        return "^$";
    }
    String ret = "^";
    for (int i = 0; i < n; i++)
        ret += "#" + s.charAt(i);
    ret += "#$";
    return ret;
}

// 马拉车算法
public String longestPalindrome2(String s) {
    String T = preProcess(s);
    int n = T.length();
    int[] P = new int[n];
    int C = 0, R = 0;
    for (int i = 1; i < n - 1; i++) {
        int i_mirror = 2 * C - i;
        if (R > i) {
            P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
        } else {
            P[i] = 0;// 等于 R 的情况
        }

        // 碰到之前讲的三种情况时候，需要利用中心扩展法
        while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
            P[i]++;
        }

        // 判断是否需要更新 R
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }

    }

    // 找出 P 的最大值
    int maxLen = 0;
    int centerIndex = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2; //最开始讲的求原字符串下标
    return s.substring(start, start + maxLen);
}

第一次写关于算法相关的解释，写的不好，请大佬们多多指点。本文参考了leetcode的题解，链接也放到最下面啦。
作者：windliang
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/