字符串str中，最长回文子串的长度如何求解？如何做到时间复杂度O(N)完成？

如果用原始的方法，只能找到奇回文，偶回文找不到。
用Manacher可以解决，需要给每一个字符前后加一个字符，例如：#a#b#c#

这个字符可以是任意字符，因为它是实对实，虚对虚。

回文直径：以一个中心点往左右两边扩的大小是回文直径。
回文半径：回文直径的一半是回文半径。
之前扩的所有位置中所到达的最右回文右边界，还需要配合回文中心点。（也就是回文最大的中心点和它所对应的回文半径）
原始字符串：a121b，处理后：#a#1#2#1#b#
回文直径：7，回文半径：4，以2往左边或者右边数就是回文半径
Manacher在向外扩展的过程整体跟之前的算法相似，但是有加速。
【步骤】

  1. 回文右边界R不包含位置i，此时暴力扩展，直到R包含i。
  2. i位置在回文有边界内时，知道了回文右边界可以知道回文左边界，对称中心为c，此时关于c做i的对称点i‘，若i‘的回文彻底在c为中心的回文里面，此时i的回文半径和i’的回文半径相同。
  3. i位置的对称位置i’的回文半径越过了以c为中心的左边范围。（i‘扩出的范围以c为中心的回文没包住，存在一部分在回文直径外面）此时i的回文半径是R-i。
  4. 正好i‘的回文半径正好跟左边L相等，此时可以直到i的回文半径大于等于i-R，然后需要判断R后面的位置，重新返回第一步。

  5. 整个算法的复杂度O(n)，虽然第一步和第四步花费时间长，但是1，4都会扩展R，依次变化的过程中，R最多也就是变化到n，所以时间复杂度为O(n)。

    1. public class Manacher {
    3.  public static char[] manacherString(String str) {
    4.      char[] charArr = str.toCharArray();
    5.      char[] res = new char[str.length() * 2 + 1];
    6.      int index = 0;
    7.      for (int i = 0; i != res.length; i++) {
    8.          res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    9.      }
    10.      return res;
    11.  }
    13.  public static int maxLcpsLength(String str) {
    14.      if (str == null || str.length() == 0) {
    15.          return 0;
    16.      }
    17.      char[] charArr = manacherString(str); // 1221 -> #1#2#2#1#
    18.      int[] pArr = new int[charArr.length]; // 回文半径数组
    19.      int C = -1; // 中心
    20.      int R = -1; // 回文右边界的再往右一个位置 最右的有效区是R-1位置
    21.      int max = Integer.MIN_VALUE; // 扩出来的最大值
    22.      for (int i = 0; i != charArr.length; i++) { // 每一个位置都求回文半径
    23.          // i至少的回文区域，先给pArr[i]
    24.          pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
    25.          while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
    26.              if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
    27.                  pArr[i]++;
    28.              else {
    29.                  break;
    30.              }
    31.          }
    32.          if (i + pArr[i] > R) {
    33.              R = i + pArr[i];
    34.              C = i;
    35.          }
    36.          max = Math.max(max, pArr[i]);
    37.      }
    38.      return max - 1; // #1#2#1# 的回文半径是4，实际的是 121   3
    39.  }
    41.  public static void main(String[] args) {
    42.      String str1 = "abc1234321ab";
    43.      System.out.println(maxLcpsLength(str1));
    44.  }
    45. }

    image.png
    Manacher算法可以分为两种情况

  6. 回文中心点没有在回文右侧的回文半径里，直接以回文中心点为中心暴力往两边扩

  7. 回文中心点在回文最右边界里

image.png
第二种情况又分为三种小情况

  1. i的回文半径在L......R里，i的回文半径一定和i的一样
  2. i`的回文半径有一部分没有在L….R内

image.png
此时i的回文半径是i——R的距离

  1. i`的左回文半径和L相同，也就是压线

image.png