Summary
马拉车算法

1. 总结
2. 回文
3. 最长回文子串
4. 经典解法: Time O(N^2)
5. 回文半径和回文直径
6. Manacher: Time O(N)
   6.1 参数设置
   6.2 流程
   6.2.1 情况1：当前匹配的字符的位置不在之前匹配的字符的回文区域的最右边界中
   6.2.2 情况2：当前匹配的字符的位置在之前匹配的字符的回文区域的最右边界中
   6.2.2.1 情况2-1：i‘ 的回文区域完全在L~R的内部
   6.2.2.2 情况2-2：i‘ 的回文区域有一部分在 L~R 的外部
   6.2.2.3 情况2-3：i‘ 的回文区域的左边界正好和 L 重合
   6.3 实现
7. 时间复杂度
8. 更多应用

1. 总结

Manacher算法和KMP算法都是解决字符串相关题目的常见算法原型，但是各自解决的问题却不一样。

Manacher算法一开始是专门用来解决 "字符串中最长回文子串问题" 的，实际上Manacher算法中有一个非常重要的信息，使用它可以解决很多其他问题，这个信息就是：每一个位置的最长回文半径。

2. 回文

回文通俗的来说就是正着看和反着看内容相同。

回文的定义是存在一个对称轴，左部分是右部分的逆序（右部分是左部分的逆序）。

例如字符串 "abcba" 和 "abba" 都是回文。

3. 最长回文子串

求最长回文子串实际上就是在一个字符串中，求哪一个子串是回文，并且是最长的。

子串中每一个字符都要求是连续的（如果字符不是连续的则是子序列）。

例如一个字符串 "abc1232de1" 中，最长回文子串是："232"。

4. 经典解法: Time O(N^2)

我们可以自己脑补一个方法，比如将字符串中的每一位字符都当作对称轴，然后同时向左右两边开始匹配。这种方法有一个明显的问题，就是如果回文子串的长度是偶数，那么是没有办法检测出来的，因为长度是偶数的回文串实际上对称轴是 "虚" 的，无法实际定位。

假设当前字符串是 "122131221"。如果使用我们原来脑补的方法，则 "1221" 回文子串就不会被检测到。

我们将原来脑补的方法进行改进，在匹配前先对原始字符串进行处理。处理方式是：字符串左右两头加 "#"，每两个字符中间加 "#"。处理成："#1#2#2#1#3#1#2#2#1#"。然后将处理之后的字符串中的每一个字符都当作对称轴，同时向左右两边开始匹配，记录回文子串长度。最后将每个位置统计的回文子串长度除以2（向下取整），对应到原字符串就是以该位置为对称轴的回文子串的长度

使用改进后的方法，无论是奇数个数的回文子串还是偶数个数的回文子串都可以被检测到。

辅助字符是什么都行，不会影响最后的答案。因为无论是以处理后的字符串的哪一个字符作为对称轴向左向右开始匹配，永远都是辅助字符和辅助字符比，真实字符和真实字符比。

public static int plalindrome(String str) {
    if (str == null || str.length() == 0) {
        return -1;
    }
    char[] c = str.toCharArray();
    char[] newC = new char[c.length * 2 + 1];
    newC[0] = '#';
    // c的指针
    int i = 0;
    // newC的指针
    int j = 1;
    // 使用辅助字符#处理原字符串
    while (i < c.length && j < newC.length - 1) {
        newC[j ++] = c[i ++];
        newC[j ++] = '#';
    }
    return process(newC);
}

public static int process(char[] str) {
    // 回文区域数组
    int[] next = new int[str.length];
    //构建回文区域数组
    for (int i = 0; i < str.length; i ++) {
        int j = i - 1;
        int k = i + 1;
        // 回文区域最少是1，为本身
        int count = 1;
        // 向两边每个字符进行匹配
        while (j >= 0 && k != str.length) {
            if (str[j] != str[k]) {
                break;
            }
            j --;
            k ++;
            count = count + 2;
        }
        next[i] = count;
    }
    // 回文区域数组升序排序
    Arrays.sort(next);
    // 回文区域数组中最大的元素除以2就是最大回文子串长度
    return next[next.length - 1] / 2;
}

时间复杂度
我们举一个最坏的例子，原字符串为："1111111"。经过我们处理后是："#1#1#1#1#1#1#1#"。

在以处理后的字符串中每一个字符为对称轴同时进行左右匹配时，由于每一次比对都会相等，因此如果当前作为对称轴的字符在左半边，则一定会匹配到最左边界；如果当前作为对称轴的字符在右半边，则一定会匹配到最右边界。

因此，假设原字符串长度为N，那么时间复杂度为：O(N^2)。我们需要对这种经典方法进行优化，从而创造了Manacher算法。

5. 回文半径和回文直径

• 回文半径：从对称轴开始向左或向右衍生，直到回文区域边界后统计的字符总数。

• 回文直径：从对称轴开始向左向右衍生，直到回文区域边界后统计的字符总数。

  
  
  回文半径和回文直径

6. Manacher: Time O(N)

6.1 参数设置

Manacher算法设计中有三个重要点：

1. 需要给被辅助字符处理的字符串中的每一个字符计算回文半径，从而构建一个回文半径数组。
2. 设置一个变量 R，记录之前匹配回文区域的所有字符中，回文边界达到的最右下标（初值为-1）。R 永远是只增不减的，只要有字符的回文更靠右，下标就会更新给 R。

R值更新

3. 设置一个变量 C，和 R 一起用，记录当前取得最右下标的回文区域的中心点的下标（初值为-1，如果最右下标重合，按照原中心点的下标）。C 也是永远只增不减的，R 更新 C 一定更新，R 不更新 C 一定不更新。

   
   
   C值更新

6.2 流程

首先需要构建回文半径数组，在构建回文半径数组时，会遇到两种大情况：

6.2.1 情况1：当前匹配的字符的位置不在之前匹配的字符的回文区域的最右边界中

该情况无优化，只能从该中心点开始同时向两边暴力扩展匹配，同时计算出该字符的回文半径。

情况1

6.2.2 情况2：当前匹配的字符的位置在之前匹配的字符的回文区域的最右边界中

如上图当 R=2 时的情况

当第二种大情况出现的时候，一定存在下图表示的通用拓扑结构：

情况2

i 为当前匹配的字符的位置，i‘ 是以 C 为对称轴所作的 i 的对称点。C、L 和R 一定都存在。

i 和 C 是不可能重合的，因为 C 表示的是 i 之前字符构建的最长回文子串的中心点。当遍历到 i 位置时，C 一定已经遍历过了。

按照 i’ 的回文区域的状况可以将第二种大情况划分成三种具体的情况，每一种情况都有单独的优化。

6.2.2.1 情况2-1：i‘ 的回文区域完全在L~R的内部

此时，i 的回文半径就是 i’ 的回文半径。

情况2-1

回文判断

在 i 位作与 i‘ 等量的区域 c~d。由于整个 L~R 是一个以 C 为中心的回文串，因此 a~b 和 c~d 一定关于 C 对称，从而 c~d 一定是 a~b 的逆序。而 a~b 是回文串，且回文串的逆序也是回文串，因此 c~d 最少一定与 a~b 等规模。为什么 c~d 不能更大？需要证明。

设置 a~b 区域前一个字符为 X，后一个字符为 Y；设置 c~d 区域前一个字符为 Z，后一个字符为 K。
为什么 i’ 当时没有将自己的回文区域扩的更大？
原因只有一个，就是X != Y。
又因为X和K对称，Y 和 Z 对称，因此 X == K，Y == Z。
所以Z != K，i 的回文区域也无法再扩大。

6.2.2.2 情况2-2：i‘ 的回文区域有一部分在 L~R 的外部

此时，i 的回文半径就是 i~R。

情况2-2

回文判断

L 作 i’ 的对称点 L'，R 作 i 的对称点 R'。
L~L‘ 和 R~R’ 一定是逆序关系，L~L‘ 是回文，因为 L~L’ 在 L~R的内部，因此 R~R’ 一定也是回文，因此 i 的回文区域至少与 L~L’ 等规模。为什么 R~R’ 不能更大？需要证明。

设置L~L‘ 前一个字符为X，L~L‘ 后一个字符为Y；R~R’ 前一个字符为Z，R~R’ 后一个字符为R。
因为 X 和 Y 都在 i‘ 的回文区域中，且关于 i’ 对称，所以X == Y。
又因为 Y 和 Z 都在 C 的回文区域中，且关于 C 对称，所以Y == Z。
为什么当时 C 没有将自己的回文区域扩的更大？
原因只有一个，就是X != K。
所以Z != K，i 的回文区域也无法再扩大。

6.2.2.3 情况2-3：i‘ 的回文区域的左边界正好和 L 重合

此时，不能直接得出 i 的回文半径，只能确定回文半径最小就是 i~R。能不能更大，需要从 i 位置向外扩展匹配。
但是此时可以设计一个常数加速，因为 i~R 是确定的最小回文半径，因此可以直接从 R 开始继续向外扩展匹配。

情况3-3

6.3 实现

class Solution {
    public boolean checkIfPangram(String sentence) {
        
    }
}

public static int plalindrome(String str) {
    if (str == null || str.length() == 0) {
        return -1;
    }
    char[] c = str.toCharArray();
    char[] newC = new char[c.length * 2 + 1];
    newC[0] = '#';
    // c的指针
    int i = 0;
    // newC的指针
    int j = 1;
    // 使用辅助字符#处理原字符串
    while (i < c.length && j < newC.length - 1) {
        newC[j ++] = c[i ++];
        newC[j ++] = '#';
    }
    return process(newC);//1221 -> #1#2#2#1#
}

public static int process(char[] str) {
    // 这里的R和定义中有些不同，这里是指i之前字符的回文区域最右边的下标的后一位，也就是说R-1才是回文区域最右边的下标
    int R = -1;
    // 中心
    int C = -1;

    // 回文半径数组
    int[] next = new int[str.length];

    for (int i = 0; i < str.length; i ++) {
        // 先确定所有情况中最低回文半径
        // 如果i > R，表示第一种大情况，最低回文半径为自身为1
        // 如果 i < R，表示第二种大情况：
        // 如果是第①种小情况，i'的回文半径会比R-i小，直接可以确定为i'的回文半径
        // 如果是第②种小情况，i’的回文半径会比R-i大，直接可以确定为R-i
        // 如果是第③种小情况，i’的回文半径和R-i相等，虽然不能确定最终的回文半径，但是可以确定最少就是i'的回文半径或R-i
        next[i] = i < R ? Math.min(next[2 * C - i], R - i) : 1;

        // 无论是遇到哪一种情况都会尝试着往外扩，因为只有第一种大情况和第二种大情况的第③种小情况需要向外扩，因此如果是第二中大情况的
        // 第①种小情况或者第②种小情况虽然也会走向外扩的流程，但是第一次就会失败，从而跳出循环。
        // 这是为了省略多个if-else所做的一个统一的流程，优化了代码的长度，并不会影响时间复杂度
        while (i + next[i] < str.length && i - next[i] >= 0) {
            if (str[i + next[i]] == str[i - next[i]]) {
                next[i] ++;
            } else {
                break;
            }
        }

        // 判断R和C是否需要更新
        if (i + next[i] > R) {
            // R向右扩
            R = i + next[i];
            // 此时i就是当前所有字符的回文区域达到最右的区域的中心点
            C = i;
        }
    }

    // 给next数组排序，找到最大的回文半径
    Arrays.sort(next);
    int maxPalindromeRadius = next[str.length - 1];

    // 处理串中i位的回文半径长度 - 1 = 原串中以i为对称轴的回文子串长度
    return maxPalindromeRadius - 1;
}

7. 时间复杂度

伪代码

public static int process(char[] str) {
    int R = ?;
    int C = ?;

    int[] next = new int[str.length];

    for (int i = 0; i < str.length; i ++) {
        if (i在R的外面) {
            从i开始向两边暴力扩;R变大
        } else { // i在R的里面
            if (i'的回文区域完全在L~R中) {
                // O(1)的操作
                返回i'的回文半径; 
            } else if (i'的回文区域的左边界在L的左边) {
                // O(1)的操作
                返回R-i; 
            } else { // i'的回文区域的左边界与L重合
                从R之外的字符开始向外扩，然后确定pArr[i]的答案;
                如果第一步扩失败，R不变；否则R变大
        }
    }
                          
    排序获得最长的回文半径处理成原文的回文串长度返回 
}

第一种大情况，和第二种大情况的第③种小情况需要向外扩充匹配，因此必定会失败1次。

第二种大情况的第①种小情况和第②种小情况是不需要向外扩充匹配的，因此失败0次。

因此每个位置扩充失败的代价是O(N)。

根据上述伪代码，不看失败，只看成功。假设字符串长度为N，以 i 和 R 作为参考标注：

情况分析

i 只增不减，R 也是只增不减。

我们将扩的行为和 R 变大绑定到一起，每一次扩，R 都会变大，R变大的总幅度就是扩成功的次数。而扩失败的次数，是可以估计出来一个总的量，就是O(N)。

因此整个时间复杂度为O(N)。

8. 更多应用

Manacher算法可以解决最大回文子串的问题，但远远不仅于此，通过回文半径数组next的信息可以解决非常多的回文问题。

回文半径数组是Manacher算法的灵魂，所以一定要清楚在每一次使用到Mancher算法时，回文半径数组的求法。