前面我們講過一個關于字串的演算法：KMP演算法，今天我們來講另外一個字串演算法：Manacher演算法，這個演算法是用于解決一個問題叫：最長回文子串，

前期文章：KMP演算法

牛客網OJ鏈接

說的簡單一點，給定一個字串，回傳的值是這個字串的最長回文子串的長度，顧名思義，即是回文串，也是子串，

一、BF演算法

那上圖的示例2為例：abc1234321ab，

最簡單的思路就是從左到右遍歷每一個字符，每來到一個字符位置，我們可以向左右兩邊進行擴展，分別比較左右兩邊的字符，如果相等，就繼續向兩邊擴展；如果不相等，就停止，計算以當前字符，向兩邊擴展出的長度，就是以當前字符為中心的回文子串，比如：

就像上圖這樣，從左往右依次遍歷即可，

上面這種思路確實能夠解題，但是還有一個很重要的點，那就是假設給定的字串是偶數個字符，那么這種方式就會錯過一些回文子串的匹配，因為此時對于偶數個字符來說，對稱點是在中間兩個字符之間的，如下圖：

所以以每個字符為中心點，向兩邊擴展，還是存在著一定的問題，如何解決呢？

那就是將原字串進行處理，加工為一個含有特殊字符的字串，比如原字串為：123321,；加工后的字串為：#1#2#3#3#2#1#；

也就是說，在每個字符的中間，加入其它字符，這樣就能使一個偶數個字符的字串，轉換為奇數個字符的字串，這樣就可以遍歷，向兩邊擴展了，

問題：我們所加入的字符，必須是原字符中沒有的字符嗎？

這個問題留作大家思考，

public static int getLengthOfSubString(String str) {
    if (str == null) {
        return 0;
    }

    char[] generateStr = generateString(str);
    int length = generateStr.length;
    int max = 0; //答案
    
    for (int i = 0; i < length; i++) {
        int tmp = 1; //每個字符都能以自己本身的字符作為回文子串，所以初始值是1
        int radius = 1; //回文半徑，也就是以i位置為中心，半徑radius的范圍內

        while (i - radius >= 0 && i + radius < length) { //左右兩邊都在陣列的范圍內，回圈繼續
            if (generateStr[i - radius] == generateStr[i + radius]) {
                tmp += 2; //左右兩個字符相等的情況
                radius++; //回文半徑加1
            } else {
                break;
            }
        }

        max = Math.max(max, tmp); //判斷當前的tmp是否是最長的回文子串
    }
    return max / 2; //因為我們比較的處理后的字串，計算出的回文串要除以2.才是最終的答案
}

public static char[] generateString(String str) {
    char[] res = new char[str.length() * 2 + 1]; //原2倍長度，再加1
    int index = 0;
    for (int i = 0; i < res.length; i++) {
        //奇數位置放#，偶數位置放原字符
        res[i] = (i % 2) == 1? str.charAt(index++) : '#';
    }
    return res;
}

以上代碼就是BF演算法，暴力解，每個字符都需要遍歷一次，而每次字符都需要向外擴展，最壞情況下，就是向外擴展一直到整個字串結束，比如：1111111； 這種情況就是每個字符向外擴展，都會擴展很長，甚至是擴展至字串結束，所以這個BF演算法的時間復雜度是O(N²) ，

二、Manacher演算法

Manacher演算法也是在BF演算法的基礎之上，做了優化，所以大家看Manacher演算法之前，先理解BF暴力解的流程，

Manacher演算法引入了三個概念：

• 當前回文子串的中心點 ：C
• 當前已經遍歷到最長回文子串的最右邊界下標：R
• 回文半徑陣列；（用于存盤已經擴展完成的回文子串的半徑）

通過上面三個變數，我們就能解決這一難題了，話不多說，講述推導程序，整體分為兩個大步驟，C和R的初始值都是-1，也就是陣列最左邊的外面，

1. 當i位置（當前遍歷的字符）不在R（最右邊界）內時：

   

   此時這種情況，我們只能向左右兩邊進行擴展，這個沒辦法，重要的是第2種情況，

2. 當i位置（當前遍歷的字符）在R（最右邊界）內時：

   

   以7為中心，向兩邊擴展出來的回文子串，就是橙色括號圈起來的范圍，此時的i就是在R邊界的里面，

   當我們以中心點為對稱點，做出i的對稱點，如下圖：

   

   做出來的對稱點，我們就能得到這個點的下標，然后去回文半徑陣列里查這個下標對應的回文半徑，就能得到關于這個對稱點的回文子串，例如上圖中黑色虛線框中的值，

   對于黑色虛線框的值，我們又可以分為三種小情況：

   • 黑色虛線框與以C中心點擴展的回文子串壓線：

     壓線的情況，就是上圖中這種情況，黑色虛線框的左邊界與橙色線重合， 根據對稱性，因為黑色虛線框的值是回文子串，那么右邊以i為中心，也能擴展出回文子串，如下圖所示：

     

     所以我們可以直接通過對稱點i得到已經完成匹配的回文子串，然后我們可以直接從i位置的已經計算好的回文子串外開始擴展，比如：左邊值7和右邊值1做比較，如果相等，當前回文半徑加1，然后繼續比較下一對字符，

   • 黑色虛線框的左邊界，超過了以C中心點擴展的回文子串的左邊界（超出）：如下圖：

     

     對稱點i，以它為中心對應的回文子串正如左邊的黑色虛線框所示：2,3,4,3,2，此時虛線框已經超出了橙色線的范圍，又因為橙色線范圍內是一個回文子串，所以我們可以推匯出當前i位置，至少有回文子串，就是（R-i）為半徑的范圍，即上圖右邊黑色虛線框內，

     此時我們只需要在此基礎之上，比較R右邊的值5 和 黑色虛線框左邊的2，看是否相等，若相等，則再次比較下一對字符，依次類推，

   • 黑色虛線框整體，都是在以C中心點擴展的回文子串的左半部分（即沒壓線，也沒超出）：如下圖：

     

     此時以i位置為中心，向左右兩邊擴展，就可以從黑色虛線框兩邊開始比較字符了，

   上面三種情況，都是由對稱點i得到關于該點的回文子串；再對稱到右邊i位置，以此為基礎，繼續向外擴展比較字符，那可能有同學就會疑惑，為什么就能從左邊對稱點i，就能推匯出右邊i位置的回文子串呢？ 證明如下：

   

上述所有，就是Manacher的推導程序，就是通過對稱，拿到C點左邊的對稱點，就能從回文半徑陣列中拿到該位置的回文子串，因此就能對應到C點右邊的回文子串，在此基礎之上進行字符比較，節省了一些已經比較過的字符的時間，

public static int manacherStr(String str) {
    if (str == null || str.length() < 1) {
        return 0;
    }

    char[] s = generateString(str);
    int length = s.length;
    int C = -1; //回文子串的中心點
    int R = -1; //最長回文子串的右邊界
    int[] pArr = new int[length]; //回文半徑陣列
    int max = 0; //答案
    for (int i = 0; i < length; i++) {
        //判斷i是否在R的范圍內，如果不在，選擇相應的對稱點，
        pArr[i] = i < R? Math.min(R - i, pArr[2 * C - i]) : 1; 

        //以下回圈，就是上面上面分析的3種小情況，也可以自己用if else陳述句
        while (i - pArr[i] >= 0 && i + pArr[i] < length) {
            if (s[i - pArr[i]] == s[i + pArr[i]]) { //左右兩邊的字符
                pArr[i]++; //回文半徑加1
            } else {
                break;
            }
        }

        //更新 新的回文子串的右邊界和 C中心點
        if (i + pArr[i] > R) {
            R = i + pArr[i];
            C = i;
        }
        max = Math.max(max, pArr[i]); //判斷是否是最長回文半徑
    }

    return max - 1; //最終的答案，與max的值，相差1
}

public static char[] generateString(String str) {
    char[] res = new char[str.length() * 2 + 1]; //原2倍長度，再加1
    int index = 0;
    for (int i = 0; i < res.length; i++) {
        //奇數位置放#，偶數位置放原字符
        res[i] = (i % 2) == 1? str.charAt(index++) : '#';
    }
    return res;
}

上述所有，就是Manacher演算法的全部，Manacher就是在BF演算法基礎之上，新加了回文半徑陣列，對于這個陣列來，可以解決很多關于字串的問題，所以很好的掌握這個演算法，對以后刷題有很大的幫助，

好啦，本期更新就到此結束啦！！！我們下期見！！！