題目

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"
  

思想

這里來(lái)說(shuō)一下O(n)來(lái)解決最長(zhǎng)回文串的問(wèn)題，即Manacher算法

那么首先需要說(shuō)一個(gè)O(n^{2)的方法，然后才能體會(huì)O(n)的方法的真正巧妙的地方在哪里。O(n}2)的方法是枚舉一個(gè)中心點(diǎn)i，然后向左右兩邊查找，直到發(fā)現(xiàn)Str[i-k]與Str[i+k]不相等了，或者是越界了，再開始下一次中心點(diǎn)的枚舉。然后對(duì)于"baab"這樣沒有中心點(diǎn)的對(duì)稱回文，又要用相同的方法再做一次（中心點(diǎn)變成兩個(gè)）。

大家就會(huì)發(fā)現(xiàn)如果遇到了像"cccccc"，這樣多次重復(fù)的串，那么一個(gè)位置就會(huì)被重復(fù)訪問(wèn)多次，這就是它很慢的根本原因，并且奇偶分別解決的話也非常的麻煩。那么我們就需要想辦法來(lái)規(guī)避掉這兩個(gè)問(wèn)題。對(duì)于搜索狀態(tài)的重復(fù)性的解決方案一般就是利用DP（對(duì)于無(wú)后效性的問(wèn)題）。那么我們就使用DP的思想再來(lái)思考一下這個(gè)問(wèn)題，就會(huì)發(fā)現(xiàn)有一些狀態(tài)是可以被繼承的。因?yàn)檫@是回文串，那么就會(huì)出現(xiàn)a與b關(guān)于c成鏡像的情況，進(jìn)一步在以c為中心的回文串當(dāng)中，以a為中心的回文串和以b為中心的回文串一定是相同的。（這里沒看懂不要緊，后面會(huì)具體畫圖分析）

那么我們就利用這個(gè)特性，就能解決掉重復(fù)訪問(wèn)的問(wèn)題。對(duì)于奇偶的問(wèn)題，我們就可以使用插入'#'號(hào)的方法來(lái)規(guī)避掉。（這個(gè)辦法真是太巧妙了）

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

這樣就把奇偶的回文串全部轉(zhuǎn)化成了奇數(shù)的回文串。

好了，那下面進(jìn)入正題，怎么解決掉重復(fù)訪問(wèn)的問(wèn)題？

• 我們可以先證明一個(gè)命題：RL[i]表示在變形字符串中以i為中心的回文串的半徑，RL[i]-1是在原字符串中以Str[i]為中心的最長(zhǎng)回文串的長(zhǎng)度

例如：bacab => #b#a#c#a#b#
原字符串的長(zhǎng)度為5，變形后的長(zhǎng)度為11。
RL[6] = 6，即在變形串中以c為中心的最長(zhǎng)回文串的半徑為6。
那么整個(gè)回文串的長(zhǎng)度應(yīng)為L(zhǎng) = 2 * RL[6] -1。
因?yàn)樵摶匚拇孜脖囟?#'，所以隨便去掉首部或者尾部的'#'后，該回文串為原回文串長(zhǎng)度的2倍。
所以原回文串長(zhǎng)度L` = [2 * RL[6] - 2] / 2 = RL[6] - 1

• 那么我們的任務(wù)也就是快速計(jì)算RL數(shù)組了，這里就需要用到前面提到的思想。首先我們來(lái)設(shè)幾個(gè)值，maxRight（現(xiàn)在能觸及到的最右邊的位置），pos（觸及到最右邊位置時(shí)回文中心的index），i（計(jì)算RL數(shù)組的枚舉變量）。
  
  • i <= maxRight :
    
    • 這時(shí)我們觀察上圖可以發(fā)現(xiàn)在兩個(gè)紅格子之間的所有格子都是關(guān)于pos對(duì)稱的，也就是i也有關(guān)于pos對(duì)稱的點(diǎn)。那我們可以計(jì)算出i關(guān)于pos的對(duì)稱點(diǎn)j = 2 * pos - i。
      
    • 這時(shí)候又要分為兩種情況，第一種是pos - j + 1> RL[j]，即j的回文串半徑?jīng)]有超過(guò)MaxRight的鏡像。這時(shí)就很簡(jiǎn)單了，因?yàn)槎际顷P(guān)于pos對(duì)稱的，那么i的回文串和j的回文串也是對(duì)稱的。RL[i] = RL[j]

    • 那第二種情況，j的回文串半徑超過(guò)了MaxRight的鏡像。那么i只能繼承j在這個(gè)鏡像區(qū)域的部分，并且繼承之后需要繼續(xù)向兩邊擴(kuò)展。這里需要注意因?yàn)樾枰^續(xù)擴(kuò)展，那么就很有可能會(huì)刷新maxRight值和pos值。

      
      
  • i > maxRight :
    
    • 這種情況就很簡(jiǎn)單了，因?yàn)閕已經(jīng)超過(guò)了maxRight，那么就不能繼承鏡像的任何東西。就只能自己向兩邊擴(kuò)展了。這里也可能會(huì)刷新maxRight的pos的值。

以上圖片均來(lái)自網(wǎng)上博客

代碼

  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 關(guān)于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;
  }

代碼不夠精簡(jiǎn)，后續(xù)會(huì)更新一個(gè)精簡(jiǎn)版

復(fù)雜度分析

以上進(jìn)行了算法的分析，那最后分析一下這種算法的復(fù)雜度和在O(n^2)算法的基礎(chǔ)上的提高。

• 關(guān)于Manacher算法的時(shí)間復(fù)雜度分析具體可以參見：知乎-如何證明Manacher算法的時(shí)間復(fù)雜度是O(n)?
• 我僅僅簡(jiǎn)單說(shuō)說(shuō)我的想法，在每一次循環(huán)當(dāng)中會(huì)涉及到一個(gè)問(wèn)題，maxRight會(huì)不會(huì)被向右推動(dòng)，如果maxRight不被向右推動(dòng)，那么這次循環(huán)O(1)能夠完成。如果maxRight被向右推動(dòng)，理論上是O(n)才能完成，但是因?yàn)槟苓M(jìn)行繼承，所以這個(gè)值遠(yuǎn)小于n，并且當(dāng)maxRight達(dá)到n時(shí)，整個(gè)算法結(jié)束。所以n會(huì)被分散在每次推動(dòng)的復(fù)雜度中的。
• 現(xiàn)在再回過(guò)頭來(lái)看整個(gè)算法，主要是在O(n^2)算法的基礎(chǔ)之上利用了繼承前面的計(jì)算結(jié)果來(lái)減少一個(gè)元素的多次訪問(wèn)問(wèn)題。并且很巧妙的利用了回文串的鏡像原理。