LeetCode 5

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

样例

• Example 1

  Input: "babad"
  
  Output: "bab"
  
  Note: "aba" is also a valid answer.
  

• Example 2

  Input: "cbbd"
  
  Output: "bb"
  

思想

这里来说一下O(n)来解决最长回文串的问题，即Manacher算法

那么首先需要说一个O(n^{2)的方法，然后才能体会O(n)的方法的真正巧妙的地方在哪里。O(n}2)的方法是枚举一个中心点i，然后向左右两边查找，直到发现Str[i-k]与Str[i+k]不相等了，或者是越界了，再开始下一次中心点的枚举。然后对于"baab"这样没有中心点的对称回文，又要用相同的方法再做一次（中心点变成两个）。

大家就会发现如果遇到了像"cccccc"，这样多次重复的串，那么一个位置就会被重复访问多次，这就是它很慢的根本原因，并且奇偶分别解决的话也非常的麻烦。那么我们就需要想办法来规避掉这两个问题。对于搜索状态的重复性的解决方案一般就是利用DP（对于无后效性的问题）。那么我们就使用DP的思想再来思考一下这个问题，就会发现有一些状态是可以被继承的。因为这是回文串，那么就会出现a与b关于c成镜像的情况，进一步在以c为中心的回文串当中，以a为中心的回文串和以b为中心的回文串一定是相同的。（这里没看懂不要紧，后面会具体画图分析）

那么我们就利用这个特性，就能解决掉重复访问的问题。对于奇偶的问题，我们就可以使用插入'#'号的方法来规避掉。（这个办法真是太巧妙了）

baab => #b#a#a#b#
bacab => #b#a#c#a#b#

这样就把奇偶的回文串全部转化成了奇数的回文串。

好了，那下面进入正题，怎么解决掉重复访问的问题？

• 我们可以先证明一个命题：RL[i]表示在变形字符串中以i为中心的回文串的半径，RL[i]-1是在原字符串中以Str[i]为中心的最长回文串的长度

例如：bacab => #b#a#c#a#b#
原字符串的长度为5，变形后的长度为11。
RL[6] = 6，即在变形串中以c为中心的最长回文串的半径为6。
那么整个回文串的长度应为L = 2 * RL[6] -1。
因为该回文串首尾必定为'#'，所以随便去掉首部或者尾部的'#'后，该回文串为原回文串长度的2倍。
所以原回文串长度L` = [2 * RL[6] - 2] / 2 = RL[6] - 1

• 那么我们的任务也就是快速计算RL数组了，这里就需要用到前面提到的思想。首先我们来设几个值，maxRight（现在能触及到的最右边的位置），pos（触及到最右边位置时回文中心的index），i（计算RL数组的枚举变量）。
  
  • i <= maxRight :
    
    • 这时我们观察上图可以发现在两个红格子之间的所有格子都是关于pos对称的，也就是i也有关于pos对称的点。那我们可以计算出i关于pos的对称点j = 2 * pos - i。
      
    • 这时候又要分为两种情况，第一种是pos - j + 1> RL[j]，即j的回文串半径没有超过MaxRight的镜像。这时就很简单了，因为都是关于pos对称的，那么i的回文串和j的回文串也是对称的。RL[i] = RL[j]

    • 那第二种情况，j的回文串半径超过了MaxRight的镜像。那么i只能继承j在这个镜像区域的部分，并且继承之后需要继续向两边扩展。这里需要注意因为需要继续扩展，那么就很有可能会刷新maxRight值和pos值。

      
      
  • i > maxRight :
    
    • 这种情况就很简单了，因为i已经超过了maxRight，那么就不能继承镜像的任何东西。就只能自己向两边扩展了。这里也可能会刷新maxRight的pos的值。

以上图片均来自网上博客

代码

  public int extendIndex(char[] charArr, int i, int l, int r) {
    while (l - 1 >= 0 && r + 1 < charArr.length) {
      if (charArr[l - 1] == charArr[r + 1]) {
        l --;
        r ++;
      } else {
        break;
      }
    }
    return (i - l + 1);
  }

  public String longestPalindrome(String s) {
    char[] _s = s.toCharArray();
    char[] charArr = new char[_s.length * 2 + 1];
    int[] f = new int[charArr.length];
    int id = -1, maxRight = -1, ansId = 0, max = -1;
    charArr[0] = '#';
    for (int i = 1; i <= _s.length; i++) {
      charArr[i * 2 - 1] = _s[(i - 1)];
      charArr[i * 2] = '#';
    }

    for (int i = 0; i < charArr.length; i++) {
      if (i > maxRight) {
        f[i] = extendIndex(charArr, i, i, i);
      } else {
        // i 关于id的镜像
        int j = 2 * id - i;
        if (i + f[j] - 1 >= maxRight) {
          f[i] = extendIndex(charArr, i, 2 * i - maxRight, maxRight);
        } else {
          f[i] = f[j];
        }
      }
      if (i + f[i] - 1 > maxRight) {
        maxRight = i + f[i] - 1;
        id = i;
      }
      if (f[i] > max) {
        max = f[i];
        ansId = i;
      }
    }

    char[] res = new char[(max - 1)];
    int index = 0;
    for (int i = -max + 1; i < max; i++) {
      if (charArr[ansId + i] != '#') {
        res[index] = charArr[ansId + i];
        index ++;
      }
    }
    String resStr = String.valueOf(res);
    return resStr;
  }

代码不够精简，后续会更新一个精简版

复杂度分析

以上进行了算法的分析，那最后分析一下这种算法的复杂度和在O(n^2)算法的基础上的提高。

• 关于Manacher算法的时间复杂度分析具体可以参见：知乎-如何证明Manacher算法的时间复杂度是O(n)?
• 我仅仅简单说说我的想法，在每一次循环当中会涉及到一个问题，maxRight会不会被向右推动，如果maxRight不被向右推动，那么这次循环O(1)能够完成。如果maxRight被向右推动，理论上是O(n)才能完成，但是因为能进行继承，所以这个值远小于n，并且当maxRight达到n时，整个算法结束。所以n会被分散在每次推动的复杂度中的。
• 现在再回过头来看整个算法，主要是在O(n^2)算法的基础之上利用了继承前面的计算结果来减少一个元素的多次访问问题。并且很巧妙的利用了回文串的镜像原理。