最長回文子串——Manacher 算法

1. 問題定義

最長回文字符串問題:給定一個字符串，求它的最長回文子串長度。
如果一個字符串正著讀和反著讀是一樣的，那它就是回文串。

舉個?? :

• s="ababa", 最長回文長度為 5；即ababa
• s="abccb", 最長回文長度為 4，即 bccb。

2.暴力解法:

對于最長回文子串問題，最簡單粗暴辦法是:找到所有字符串的子串，遍歷每一個子串以驗證它們是否為回文串。一個子串由子串的起點和終點確定，因此對于一個長度為n的字符串，共有n^2個子串。這些子串的平均長度大約為n/2，因此這種解法的時間復雜度是O(n^3)。

解法：

string findLongestPalindrome(string &s){

   if (s.empty()) {
       return "";
    }

    if (s.size() == 1) {
        return s;
     }
    // 字符串 長度
    unsigned long length = s.size();
    // 最長 回文 字符串 長度
    int maxLength = 0;
    // 最長 回文 字符串 起始地址
    int start = 0;

    for(int i = 0; i < length; i++){
        for (int j = i + 1; j < length; j++) {
            int tmp1, tmp2;
            // 判斷 是不是 回文
            for (tmp1 = i, tmp2 = j; tmp1 < tmp2; tmp1++, tmp2--) {
                if(s.at(tmp1) != s.at(tmp2)){
                    break;
                }
            }
            // 如果 遍歷 到中間 說明這是一個 回文 字符串
            if (tmp1 >= tmp2 && (j-i) >= maxLength) {
                maxLength = j - i + 1;
                start = i;
            }
        }
    }
    if (maxLength > 0) {
        return s.substr(start, maxLength);
    }
    return "";
}

3. 動態(tài)規(guī)劃

回文字符串的子串也是回文，所以對于母串s,我們用p[i][j] = 1(表示以i開始以j結(jié)束的子串)是回文字符串，那么p[i+1][j-1]也是回文字符串。

• 這樣當s[i] = s[j]時，如果p[i+1][j-1]是回文子串，則p[i][j]也是回文子串。

• 如果p[i+1][j-1]不是回文子串或者s[i] != s[j],那么p[i][j]就不是回文子串。

• 特別地，對于這樣的字符串——只包含單個字符、或者兩個字符重復，其均為回文串

  p[i][i] = 1;
  c[i][i+1] = 1， if(s[i] == s[i+1])
  

• 這樣需要額外的空間o(N^2),算法復雜度也是o(n^2).
  解法:

    static int const arrayLength = 100;
    string findLongestPalindrome(string &s){
        if (s.empty()) {
              return "";
        }
  
        if (s.size() == 1) {
             return s;
        }
        // 字符串 長度
        unsigned long length = s.size();
        // 最長 回文 字符串 長度
        int maxLength = 0;
        // 最長 回文 字符串 起始地址
        int start = 0;
        // 存儲 所有 子字符串
        bool p[arrayLength][arrayLength] = {false};
  
        for(int i = 0; i < length; i++){
            // 單個 字符 為 回文串
            p[i][i] = true;
            // 判斷 兩個字 重復 情況
            if ((i < length - 1) && s.at(i) == s.at(i+1)) {
                p[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }
  
        // 子串 長度(因為已經(jīng)計算了單個或兩個字重復的回文字符串,所以子串長度最低從3開始)
        // 計算 3 - length 所有子串中 所有最長子串
        for(int len = 3; len <= length; len++){
            // 子串 起始 地址
            // 在 字符串 中 找到 所有 長度為 len的子串并判斷
            for (int i = 0; i <= length - len; i++) {
                int j = i + len - 1;
                if (p[i+1][j-1] && s.at(i) == s.at(j)) {
                   p[i][j] = true;
                    maxLength = len;
                    start = i;
                }
            }
        }
        if (maxLength >= 2) {
            return s.substr(start, maxLength);
        }
        return "";
       }
  

這種解法，當最大的回文子串有多個時，取最后一個，如果要取第一個，則在 start = i后面加上break;即可。

C語言解法：

static int const arrayLength = 100;
/**
 找到 最長 回文 子串 (動態(tài) 規(guī)劃 方法)
 
 @param string 字符串
 @param stringLength 字符串 長度
 */
void findLongestPalindromeTwo(char *string, int stringLength) {
    if (string == NULL || stringLength == 0) {
        return;
    }
    if (stringLength == 1) {
        printf("%s\n", string);
        return;
    }

    // 回文串 長度
    int maxLength = 0;
    // 起始 位置
    int startPosition = 0;
    // 輔助 數(shù)組(存儲 所有 字符串)
    int helperArray [arrayLength][arrayLength] = {false};
    
    // 循環(huán) 遍歷
    for (int tmpIndex = 0; tmpIndex < stringLength; tmpIndex++) {
        // 單個 字符 為 回文串
        helperArray[tmpIndex][tmpIndex] = true;
        if (string[tmpIndex] == string[tmpIndex + 1]) {
            // 相同 字符 比如 aa 也是 回文串
            helperArray[tmpIndex][tmpIndex + 1] = true;
            startPosition = tmpIndex;
            maxLength = 2;
        }
    }
    
    // 循環(huán) 遍歷
    // 子串 長度(因為已經(jīng)計算了單個或兩個字重復的回文字符串,所以子串長度最低從3開始)
    // 計算 3 - length 所有子串中 所有最長子串
    for (int len = 3; len <= stringLength; len ++) {
        for (int i = 0; i <= stringLength - len; i ++) {
            int j = i + len - 1;
            if (helperArray[i + 1][j - 1] == true && string[i] == string[j]) {
                helperArray[i][j] = true;
                maxLength = len;
                startPosition = i;
            }
        }
    }
    
    if (maxLength > 1) {
        for (int tmpIndex = 0; tmpIndex < maxLength; tmpIndex++) {
            printf("%c", string[startPosition]);
            startPosition++;
        }
        printf("\n");
    }
}

4.中心擴展

• 很明顯所有的回文字符串都是對稱的;

• 長度為奇數(shù)回文字符串以最中間字符位置為對稱軸左右對稱。

• 長度為偶數(shù)的回文串以中間兩個字符的空隙為對稱軸對稱。

• 因此，整個字符串中所有字符，以及字符間的空隙都有可能是某個回文子串的對稱軸位置?？梢员闅v這些位置，在每個位置上同時向左向右擴展，直到左右兩邊字符不同或者到達邊界。

• 對于一個長度為n的字符串，這樣的位置一共有n+n-1=2n-1個，在每個位置上平均要進行大約n/4次比較，此算法的時間復雜度為o(n^2).

解法：

    string findLongestPalindrome(string &s) {
    
        if (s.empty()) {
            return "";
        }
    
        if (s.size() == 1) {
            return s;
        }
    
        unsigned long length = s.size();
    
        int maxlength = 0;
    
        int start = 0;
    
        string tmpStr = s;
        for(int i = 0,k = 0; i <= length; i++){
            s.insert(k, "#");
            k = k + 2;
        }

        for (int i = 0 ; i < length; i++) {
            // 間隔 兩個 字符
            int j = i - 1, k = i + 1;
            while (j >= 0 && k < length && s.at(j) == s.at(k)) {
                if ((k - j + 1) > maxlength) {
                    maxlength = k - j +1;
                    start = j;
                }
                j--;
                k++;
            }
        }
    
        if(maxlength > 0){
            int tmpMaxLength = (maxLength - 1)/2;
            int tmpStartPostion = start/2;
            return tmpStr.substr(tmpStartPostion,tmpMaxLength);
        }
        return "";
    }

C語言解法:

/**
 找到 最長 回文 子串 (中心 對稱 方法)

 @param string 字符串
 @param stringLength 字符串 長度
 */
void findLongestPalindrome(char *string, int stringLength) {
    if (string == NULL || stringLength == 0) {
        return;
    }
    if (stringLength == 1) {
        printf("%s\n", string);
        return;
    }
    
    // 插入 特殊字符 后字符串 長度
    int tmpStringLength = stringLength * 2 + 1;
    // 開辟 新的字符串
    char *tmpString = malloc(sizeof(char) * tmpStringLength);
    // 新字符串 復制 舊字符串 并在空隙插入 '#'
    tmpString[0] = '#';
    for (int tmpIndex = 0; tmpIndex < stringLength; tmpIndex ++) {
        tmpString[tmpIndex * 2 + 1] = string[tmpIndex];
        tmpString[tmpIndex * 2 + 2] = '#';
    }
    
    // 回文串 長度
    int maxLength = 0;
    // 起始 位置
    int startPosition = 0;
    
    // 遍歷 字符串
    for(int i = 0; i < tmpStringLength; i++) {
        int j = i - 1;
        int k = i + 1;
        while (j >= 0 && k < tmpStringLength && tmpString[j] == tmpString[k]) {
            if (k - j + 1 > maxLength ) {
                maxLength = k - j + 1;
                startPosition = j;
            }
            j --;
            k ++;
        }
    }
    
    if (maxLength > 1) {
        int tmpMaxLength = (maxLength - 1)/2;
        int tmpStartPostion = startPosition/2;
        
        for (int tmpIndex = 0; tmpIndex < tmpMaxLength; tmpIndex++) {
            printf("%c", string[tmpStartPostion]);
            tmpStartPostion++;
        }
        printf("\n");
    }
}

5. Manacher 算法

中心擴展的算法是存在缺陷的:

• 由于回文字符串的奇偶性造成了不同性質(zhì)的對稱軸位置，因此要分兩種情況進行處理。

• 很多子串被重復多次訪問，造成較差的時間效率。
  舉個?? ：

  s : a b a b a
  i : 0 1 2 3 4
  

當i == 1和i == 2時，左邊的子串a(chǎn)ba分別被遍歷了一次。

A. 解決長度奇偶性帶來的對稱軸位置問題
Manacher算法首先對字符串做一個預處理，在所有的空隙位置(包括首尾)插入同樣的符號，要求這個符號是不會出現(xiàn)在原串中出現(xiàn)的，這樣會使得所有的串都是奇數(shù)長度的。已插入#號為例。

 aba  ———>  #a#b#a#
 abba ———>  #a#b#b#a#

插入的是同樣的符號，且符號不存在于原串，因此子串的回文性不受影響，原來是回文的串，插完之后還是回文的，原來不是回文的，依然不是回文的。

B. 解決重復訪問的問題
我們把一個回文中最左或最右位置的字符與其對稱軸的距離稱為回文半徑。Manacher定義了一個回文半徑數(shù)組RL,用RL[i]表示以第i個字符為對稱軸的回文串的回文半徑。我們一般對字符串從左往右處理，因此這里定義RL[i]為第i個字符為對稱軸的回文串的最右一個字符與字符i距離。對于上面插入分隔符之后的兩個串，可以得到RL數(shù)組。

   s:    # a # b # a #
 RL :    1 2 1 4 1 2 1
RL-1:    0 1 0 3 0 1 0
  i :    0 1 2 3 4 5 6

   s:     # a # b # b # a #
 RL :     1 2 1 2 5 2 1 2 1
RL-1:     0 1 0 1 4 1 0 1 0
  i :     0 1 2 3 4 5 6 7 8

上面我們還求了一下RL[i]-1。通過觀察可以發(fā)現(xiàn)，RL[i]-1的值，正是在原來那個沒有插入過分割符的串中，以位置i為對稱軸的最長回文串的長度。那么只要我們求出RL數(shù)組，就能得到最長回文子串的長度。

那么問題就變成了，怎樣高效地求RL數(shù)組，基本思路是利用回文串的對稱性，擴展回文串。
我們再引入一個輔助變量MaxRight,表示當前訪問到的所有回文子串，所能觸及的最右一個字符的位置。另外還要記錄下MaxRight對應的回文串的對稱軸所在位置,記為pos，它們的位置關系如下。

image.png

我們從左往右地訪問字符串來求RL,假設當前訪問到的位置是i,即要求RL[i],在對應上圖，i必然在pos右邊，但是我們更關注的是，i是在MaxRight的左邊還是右邊，我們分情況分析。

• ** 當i在MaxRight的左邊**
  如下圖所示:

image.png

我們知道，圖中兩個紅色塊之間(包括紅色塊)的串是回文的；并且以i對稱軸的回文串，是與紅色塊間的回文串有所重疊的。我們找到i關于pos的對稱位置j,這個j對應RL[i]我們已經(jīng)算過的。根據(jù)回文串的對稱性，以i為對稱軸的回文串和以j為對稱軸的回文串，有一部分是相同的。這里又有兩種細分情況。

a. 以j為對稱軸的回文串比較短，短到如下圖所示:

image.png

image.png

綜上，我們只能獲取RL[2*pos - i]和 MaxRight-1這兩者中最小的值，來保證該范圍內(nèi)的字符串是回文字符串，RL[i] = min(RL[2*pos - i], MaxRight-1),之后都要嘗試更新MaxRight和pos，因為有可能得到更大MaxRight.

具體操作如下:

step 1: 令RL[i]=min(RL[2*pos-i], MaxRight-i)
step 2: 以i為中心擴展回文串，直到左右兩邊字符不同，或者到達邊界。
step 3: 更新MaxRight和pos

• 當i在MaxRight的右邊
  遇到這種情況，說明以i為對稱軸的回文串還沒有任何一部分被訪問過，于是只能從i的左右兩邊開始嘗試擴展了，當左右兩邊字符不同或者到達字符串邊界時停止更新。然后更新MaxRight和pos。
  解法:

  string findLongestPalindrome3(string &s) {
  
        if (s.empty()) {
            return "";
        }
  
        if (s.size() == 1) {
            return s;
        }
  
        unsigned long length = s.size();
  
        int MaxRight = 0;
        int Maxlen = 0;
        int pos = 0;
        string tmpStr = s;
        for(int i = 0,k = 0; i <= length; i++){
            s.insert(k, "#");
            k = k + 2;
        }
        length = s.size();
  
        int *RL = new int[length]();
        memset(RL, 0x00, sizeof(length));
        for (int i = 0; i < length; i++) {
            if (i < MaxRight) {
                RL[i] = min(RL[2*pos - i], MaxRight-1);
            }else {
                RL[i] = 1;
            }
            while (i - RL[i] >= 0 && i+RL[i] < length && s[i - RL[i]] == s[i + RL[i]]) {
                RL[i] += 1;
            }
            if (RL[i] + i - 1 > MaxRight) {
                MaxRight = RL[i] + i - 1;
                pos = i;
            }
            Maxlen = max(Maxlen, RL[i]);
        }
        if (Maxlen > 0) {
            return tmpStr.substr((pos+1)/2 - Maxlen/2, Maxlen - 1);
        }
        free(RL);
        return "";
    }
  

C語言解法:

/**
 找到 最長 回文 子串 (拉馬車 方法)
 
 @param string 字符串
 @param stringLength 字符串 長度
 */
void findLongestPalindromeThree(char *string, int stringLength) {
    if (string == NULL || stringLength == 0) {
        return;
    }
    if (stringLength == 1) {
        printf("%s\n", string);
        return;
    }

    // 插入 特殊字符 后字符串 長度
    int tmpStringLength = stringLength * 2 + 1;
    // 開辟 新的字符串
    char *tmpString = malloc(sizeof(char) * tmpStringLength);
    // 新字符串 復制 舊字符串 并在空隙插入 '#'
    tmpString[0] = '#';
    for (int tmpIndex = 0; tmpIndex < stringLength; tmpIndex ++) {
        tmpString[tmpIndex * 2 + 1] = string[tmpIndex];
        tmpString[tmpIndex * 2 + 2] = '#';
    }
    
    
    // 記錄 最長 半徑 范圍
    int maxRight = 0;
    // 記錄 最長 回文 字符串 長度
    int maxLength = 0;
    // 當前 最長 半徑 的 對稱軸
    int currentPosition = 0;
    // 記錄 每個 位置 最長回文 長度
    int *palindromeArray = malloc(sizeof(int) * tmpStringLength);
    memset(palindromeArray, 0x00, sizeof(tmpStringLength));
    
    // 遍歷 字符串
    for (int tmpIndex = 0; tmpIndex < tmpStringLength; tmpIndex++) {
        // 當前 字符 在最大 半徑 范圍 左邊
        if (tmpIndex < maxRight) {
            if (palindromeArray[2*currentPosition - tmpIndex] > maxRight - tmpIndex) {
                palindromeArray[tmpIndex] = maxRight - tmpIndex;
            }
            else {
                palindromeArray[tmpIndex] = palindromeArray[2*currentPosition - tmpIndex];
            }
        }
        // 當前 字符 在 最大半徑 范圍 右邊(沒有被遍歷過)
        else {
            palindromeArray[tmpIndex] = 1;
        }
        
        // 在先前 計算的 回文長度 基礎 上 擴展遍歷
        while (tmpIndex - palindromeArray[tmpIndex] >= 0 &&
               tmpIndex + palindromeArray[tmpIndex] < tmpStringLength &&
               tmpString[tmpIndex - palindromeArray[tmpIndex]] == tmpString[tmpIndex + palindromeArray[tmpIndex]]) {
            palindromeArray[tmpIndex] += 1;
        }
        
        if (palindromeArray[tmpIndex] + tmpIndex - 1 > maxRight) {
            maxRight = palindromeArray[tmpIndex] + tmpIndex - 1;
            currentPosition = tmpIndex;
        }
        
        // 更新 長度
        if (maxLength < palindromeArray[tmpIndex]) {
            maxLength = palindromeArray[tmpIndex];
        }
    }
    
    if (maxLength) {
        int tmpMaxLength = maxLength - 1;
        int tmpStartPostion = (currentPosition + 1)/2 - maxLength/2;
        
        for (int tmpIndex = 0; tmpIndex < tmpMaxLength; tmpIndex++) {
            printf("%c", string[tmpStartPostion]);
            tmpStartPostion++;
        }
        printf("\n");
    }
    
}

C.復雜度分析:

• 空間復雜度:插入分隔符行程新串，占用了線性的空間大??；RL數(shù)組也占用線性 大小的空間，因此空間復雜度是線性的。

• 時間復雜度:盡管代碼里面有兩層循環(huán)，由于內(nèi)層循環(huán)只是對尚未匹配的部分進行，因此對于每一個字符而言只會進行一次，因此時間復雜度是o(n).