关于java:马拉车算法其实并不难

5次阅读

共计 2420 个字符，预计需要花费 7 分钟才能阅读完成。

要说马拉车算法，必须说说这道题，查找最长回文子串，马拉车算法是其中一种解法，狠人话不多，间接往下看：

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：输出：s = "babad"
输入："bab"
解释："aba" 同样是合乎题意的答案。示例 2：输出：s = "cbbd"
输入："bb"

示例 3：输出：s = "a"
输入："a"

示例 4：输出：s = "ac"
输入："a"

这是一个微妙的算法，是 1957 年一个叫 Manacher 的人创造的，所以叫Manacher‘s Algorithm, 次要是用来查找一个字符串的最长回文子串，这个算法最大的奉献是将工夫复杂度晋升到线性，后面咱们说的动静布局的工夫复杂度为 O(n²)。

后面说的核心拓展法，核心可能是字符也可能是字符的间隙，这样如果有 n 个字符，就有 n+n+1 个核心：

为了解决下面说的核心可能是间隙的问题，咱们往每个字符间隙插入”#“, 为了让拓展完结边界更加清晰，右边的边界插入”^“, 左边的边界插入 “$“:

S 示意插入 ”#“,”^“,”$“ 等符号之后的字符串，咱们用一个数组 P 示意 S 中每一个字符可能往两边拓展的长度:

比方 P[8] = 3，示意能够往两边别离拓展 3 个字符,也就是回文串的长度为 3，去掉 # 之后的字符串为aca：

P[11]= 4，示意能够往两边别离拓展 4 个字符，也就是回文串的长度为 4，去掉 # 之后的字符串为caac：

假如咱们曾经得悉数组 P，那么咱们怎么失去回文串？

用 P 的下标 index，减去 P[i]（也就是回文串的长度），能够失去回文串结尾字符在拓展后的字符串 S 中的下标，除以 2，就能够失去在原字符串中的下标了。

那么当初的问题是：如何求解数组 P[i]

其实, 马拉车算法的要害是：它充分利用了回文串的对称性，用已有的后果来帮忙计算后续的后果。

假如曾经计算出字符索引地位 P 的最大回文串，左边界是 P _L，右边界是 P _R：

那么当咱们求因为一个地位 i 的时候，i 小于等于 P_R, 其实咱们能够找到 i 对于 P 的对称点 j:

那么假如 j 为核心的最长回文串长度为 len，并且在 P_L 到 P 的范畴内，则 i 为核心的最长回文串也是如此：

以 i 为核心的最长回文子串长度等于以 j 为核心的最长回文子串的长度

然而这里有两个问题：

前一个回文字符串 P，是哪一个？
有哪些非凡状况？非凡状况怎么解决？

(1) 前一个回文字符串 P，是指的后面计算出来的 右边界最靠右的回文串，因为这样它最可能笼罩咱们当初要计算的 i 为核心的索引，能够尽量重用之前的后果的对称性。

也正因为如此，咱们在计算的时候，须要一直保留更新 P 的核心和右边界，用于每一次计算。

(2) 非凡状况其实就是以后 i 的最长回文字符串计算不能再利用 P 点的对称，例如：

以 i 的回文串的右边界超出了 P 的右边界 P_R:

这种状况的解决方案是：超过的局部，须要依照核心拓展法来一一拓展。

i 不在以 P 为核心的回文串外面，只能依照核心拓展法来解决。

具体的代码实现如下：

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

    // 马拉车算法
    public String longestPalindrome(String str) {String S = preProcess(str);
        int n = S.length();
        // 保留回文串的长度
        int[] P = new int[n];
        // 保留边界最右的回文核心以及右边界
        int center = 0, right = 0;
        // 从第 1 个字符开始
        for (int i = 1; i < n - 1; i++) {
            // 找出 i 对于后面核心的对称
            int mirror = 2 * center - i;
            if (right > i) {
                // i 在右边界的范畴内，看看 i 的对称点的回文串长度，以及 i 到右边界的长度，取两个较小的那个
                // 不能溢出之前的边界，否则就得核心拓展
                P[i] = Math.min(right - i, P[mirror]);
            } else {
                // 超过范畴了，核心拓展
                P[i] = 0;
            }

            // 核心拓展
            while (S.charAt(i + 1 + P[i]) == S.charAt(i - 1 - P[i])) {P[i]++;
            }

            // 看看新的索引是不是比之前保留的最右边界的回文串还要靠右
            if (i + P[i] > right) {
                // 更新核心
                center = i;
                // 更新右边界
                right = i + P[i];
            }

        }

        // 通过回文长度数组找出最长的回文串
        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 str.substring(start, start + maxLen);
    }

至于算法的复杂度，空间复杂度借助了大小为 n 的数组，为 O(n)，而工夫复杂度，看似是用了两层循环，实则不是 O(n²)，而是 O(n)，因为绝大多数索引地位会间接利用后面的后果以及对称性取得后果，常数次就能够失去后果，而那些须要核心拓展的，是因为超出后面后果笼罩的范畴，才须要拓展，拓展所得的后果，有利于下一个索引地位的计算，因而拓展实际上较少。

【作者简介】：
秦怀，公众号【秦怀杂货店 】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis， 分布式 ， 剑指 Offer，LeetCode等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。

剑指 Offer 全副题解 PDF

2020 年我写了什么？

开源编程笔记

正文完