longest palindromic substring 演算法整理 (Manacher’s algorithm)

palindrome是指一個字串的 string = reverse(string)

而longest palindromic substring則是指找出一個字串中,substring是palindrome的最長substring

這個問題brute force不難想,就是把所有的substring 列出來,檢查是不是palindrome,但是這樣worse case會是O(n^3),因為substring有O(n^2)個,檢查palindrom要O(n)

比較常見的做法是中心點展開法,也就是選取一個點,然後展開看最大可以展到多少長度

這樣的time complexity為O(n^2),共n個字元做展開,每個字元展開worst case O(n), total O(n^2)

事實上,有更好的方法Manacher’s algorithm time complexity是O(n),可以參考wiki上的說明 https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher’s_algorithm

但是Wiki上的說明實在是太難理解了,所以這邊做個整理說明,並給出一些可能的實現

Manacher’s algorithm中文又有人叫馬拉車算法,本質上還是中心點展開法,但是差異在Manacher算法中會把之前走過的展開的資訊做個紀錄,在後面的展開中直接略去從頭開始展開的步驟,直接將整個演算法步數降到O(n)

在處理palindrome時,為了要避免分開處理奇數長度palindrome 或是偶數長度palindrome,一個常見的處理方式是在字串中插入delimeter

用什麼delimiter都可以,只要不要跟原始string的char衝突就好,加了delimiter後,整個字串的長度一定是奇數,且palindrome也一定是奇數,所以不用擔心要特別偵測偶數的palindrome(偶數palidrome是偵測s[i] == s[i+1],再以i, i+1往兩側展開)

為什麼加了delimiter就保證奇數呢?可以這樣想: N個字元的字串,有N+1個空間,插入delimeter就是N+N+1 = 2N+1 保證奇數,並且觀察以上abba, aba兩個字串的palindrome,可以發現delimeter本身是對稱的,所以也是符合把palindrome空隙插滿,亦即2m+1的情況,因此也是奇數

這邊先看一下其中一個實現方式,此方法參考了 https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4/ 的思路來實現

std::string lps(const std::string& s)
{
  int len = s.size();
  int N = 2 * len + 1; //with delimiter
  std::vector<int> dp(N);
  int C = 1; //current center
  int R = 1; //palindrome right index of current center
  int maxLen = 1; // max palindrome radius (inclusive)
  int maxI = 0; //center index of max palindrome length 
  for(int i = 1; i < N; i++)
  {
    int mirrorI = C - (i-C);
    int delta = R - i;
    if(delta>0)
    {
      //based on previous information, calculate current palindromic string radius
      //also need to take account of information which is out of bound
      dp[i] = std::min(dp[mirrorI], delta);
    }
    while(( i + dp[i] < N - 1) &&
          ( i - dp[i] > 0) &&
          ( ((i + dp[i] + 1) % 2 == 0) ||
            (s[(i+dp[i]+1)/2] == s[(i-dp[i]-1) / 2])))
    {
      dp[i]++;
    }
    //update max radius
    if(dp[i] > maxLen)
    {
       maxLen = dp[i];
       maxI = i;
    }
    //update center
    if(i + dp[i] > R)
    {
      C = i;
      R = i + dp[i];
    }
  }
  int index = (maxI - maxLen)/2;
  return s.substr(index, maxLen);
}

先理解一下dp內代表的意義

dp中存了走訪的資訊,代表該index [i-j, i+j] 是以該index為中心,最長的palindrome,可以看到圖中的 a dp = 9,代表 該字元 a 往右邊9個與往左邊9個皆相同,也可以發現這個數字對應原來沒有delimiter的字串,剛好以a為中心整個palindrome長度就是9

如果我們可以得到整個dp的值,基本上答案就出來了

首先看一個範例,以下圖的箭頭處為例,該處字元a 對應的dp值應該是多少呢?

最簡單的想法就是往右走往左走,看看能比對到最長的長度,這樣就要O(n),n個字元就要O(n^2),Manacher的算法說,可以省略一些步驟,方框處是以c為中心點找到最長的palindrome,左右7 chars都對稱,這裡面隱含了一些可利用的資訊

如何找出隱含的資訊,仔細觀察在虛線c的位置,已經找到左右7個對稱,代表在某種程度,左邊看到的世界和右邊看到的世界是相同的, 圖中藍色的數字是已經算好的dp值,下排紅色的數字是從mirror看到的數字,因為對稱,代表在c的方圓內,可以保證兩方在碰到藍色框之內是相同的,藍色框外的世界不知道,這裡我們可以看到至少? 地方的longest match = 3(因為3仍然在方框內)

方框外的資訊就不知道,但是至少我們可以從方框外開始比

也就是直接跳了3步,直接從j = 4開始比,透過比較完可以知道方框往右可以延伸的地方,必要時更新new center,和new radius

看起來很繁瑣,但是只要掌握住基本的概念,利用可利用的資訊,超出邊界的不能用,邊界外的資訊再另外算的原則,就可以比較好理解

我們再來看圖中?處的值應該是多少,看mirror,應該是7,但是如果仔細看,其實對應的位置走七步是超出藍框邊界的(下圖中綠色框處),因此必須做調整,只能保證到藍框處,也就是5,接著直接從5開始比,比失敗就設定dp = 5

關於time complexity,乍看之下,上面的作法是省略了一些比較,但真的能把n^2降到n嗎?關鍵在於藍框處,會需要做超過一步的比較就代表以新的點為中心,沒有藍框以內的資訊可以用,因此新的比較是從藍框外開始比,如果有比到代表會擴展藍色框的右邊,而藍色框是一路往右的,因此整體的time complexity是O(n)

test case: 這個test case長度約一千多,如果使用一般的做法n^2約做1 million steps

實測step數 Manacher算法對上面的字串 len =1450, steps = 2897

順便附上中心點展開法的一個參考解答(來自於leetcode其他人的submission)

std::string lps(const std::string& s)
{
  if (s.size() <= 1) return s;
    int maxIdx = 0;
    int maxLen = 1;
    int i = 0;
    while (i < s.size()) {
        int start = i;
        int end = i;
        // expand the window from the end if it's an even palindrome
        while (end + 1 < s.size() && s[end] == s[end + 1]) {
           end++;
        }
        i = end + 1;
        // expand the window from both sides until it's not longer a palindrome
        while (start - 1 >= 0 && end + 1 < s.size() && s[start - 1] == s[end + 1]) {
            start--, end++;
        }
        int currLen = end - start + 1;
        if (currLen > maxLen) {
            maxIdx = start;
            maxLen = currLen;
        }
    }
    return s.substr(maxIdx, maxLen);
}

以上面test case測試,len = 1450,steps = 524902

另外也放上根據wiki 參考,直接使用delimiter作法的實現,和最一開始的實作差別是直接使用加工過的string做計算,不用額外處理index

std::string lps(const std::string& s)
{
  int len = s.size();
  int N = 2 * len + 1;
  std::vector<int> dp(N);
  std::string s2(1, '|');
  for(auto c: s)
  {
    s2.push_back(c);
    s2.push_back('|');
  }
  int C = 0;
  int R = 0;
  for(int i = 1; i < N; i++)
  {
    if(i > R)
    {
      C = i;
      R = i;
    }
    else
    {
      int mirrorI = C - (i - C);
      dp[i] = std::min(dp[mirrorI], R - i);
    }
    int j = dp[i] + 1;
    while((i-j >= 0) && (i+j < N) && (s2[i-j] == s2[i+j]))
    {
      j++;
    }
    dp[i] = j - 1;
    if(i + dp[i] > R)
    {
      C = i;
      R = i + dp[i];
    }
  }
  auto it = std::max_element(dp.begin(), dp.end());
  int maxLen = *it;
  int index = it - dp.begin();
  return s.substr((index - maxLen) / 2, maxLen);
}

總結來說,Manacher算法的核心在如何重複利用先前發掘的dp資訊,並且需要標定藍框的位置,藍框是使得Manacher可以將步數降到O(n)的關鍵,對應程式碼就是C, R變數(center, radius)

Manacher算法其實理解了後並不難,不過理解本身需要沉下心來花一點時間,不能抱著速成心態看。

This entry was posted in Algorithm. Bookmark the permalink.

Leave a Reply