[LeetCode] 用對稱圖形來理解 Manacher's Algorithm #5 Longest Palindromic Substring

-

Manacher's Algorithm 被大家形容得好像是很困難的演算法。於是我在想，有沒有辦法把 Manacher's Algorithm 用好玩的方式來理解呢?

更簡單的演算法可以參考上一篇文章。

理解 Manacher's Algorithm

對稱半徑

回文相對於圖片就是對稱圖形的概念，我們今天的目標就是找法國、加拿大、法國國旗組在一起裡面最寬的對稱圖形:


如果我們這樣切，每個地方都可以當摺線，我們可以說對稱的地方半徑是 2:


因為往左或往右都有 2 塊。

沒有對稱的地方就是 0:


當然還有另外一種對稱是不看中間的那塊，像是文字 "aba" 我們就可以不看 "b"，像是我們可以忽略楓葉中間那塊:


對稱中的對稱 (Case 1)

這大概就是 Manacher's Algorithm 裡面最核心的概念。

假設我們已經知道有一塊半徑是 6 的對稱，如果左邊有一小塊半徑 1 的對稱，那我們可以知道右邊的對稱半徑嗎?


如果你把左半邊連數字和箭頭也當圖片的話，那右半邊不就長的一樣? 那半徑也就一樣?


沒錯，這種感覺就好像蝴蝶翅膀上面比較小的圈圈自然也會對稱在另外一邊:


被砍掉的對稱 (Case 2)

那如果有對稱超過藍色對稱的範圍怎麼辦? 像是這樣:


既然藍色對稱的範圍只到那邊，就代表他的外面一定不一樣，我們當然不能 copy 左半邊的半徑:


真可惜，不過我們會發現，我們還是可以把右半邊往中間擠到藍色對稱範圍裏面就可以對稱了:


可以更寬的對稱 (Case 3)

我們再來看最後一個 case，如果左半邊剛好碰到邊緣會發生什麼事? 這邊我把加拿大國旗中間一小塊換成藍色的:


的確這和 Case 1 看起來好像沒什麼差別，一樣的對稱半徑，But...


我們如果把右半邊的對稱稍微拉長一下，會發現，哇，右半邊有可能變更長耶，左半邊卻是沒辦法:


Manacher's Algorithm 設計是當碰到這個情形就把藍色的中心點移到這個新的地方繼續跑，因為我們還沒讀到右邊邊界外，沒人知道他會變多長，這只能繼續乖乖左右慢慢拉開嘗試。

所以 Manacher's Algorithm 比 O(n^2) 演算法聰明的地方就只有重複利用上面藍色對稱的部分裡面的資訊，只要超出這個範圍，很抱歉就只好一個一個字元比較。

實作技巧

大部分網路上的解答都是和 Wikipedia 一樣先替 s 加上一堆 "#" 或是 "|"，但是為何一定要加? 我就不想加，於是我在 index 上面動手腳:


我可以設計一個 function 專門回傳 s 第幾個字元是什麼，把虛線灰色框的地方的 index 都回傳一個不存在的字元 (像是 "|") 。

這樣有什麼好處? 除了比較省記憶體也是讓設計者比較偏用 index 來設計演算法，甚至在檢查左右字元是不是一樣你只要看 index 是偶數其實就可以跳過不用真的去抓字元，少了一次存取和比較。

演算法

Step 1 我們都是學 O(n^2) 演算法一樣左右找最長的對稱，找到後就把右半邊根據上面說的 Case 1, 2, 3 來 reuse 左半邊的資訊，直到 Case 3 發生:


Case 3 發生怎麼辦? 那就從這個地方繼續跑 Step 1，但可以跳過一些距離不用判斷:


C++ 程式碼

這次的程式碼我就真的是先設計出上面的投影片再來實作的 (之前幾次都是先寫 code 、再來做投影片、再來寫部落格)。對我來說上面的圖像對稱概念已經變成我記憶宮殿中一部分了，一個月後再來問我我還是寫得出來:


#include <cmath>

class Solution {
 public:
  std::string longestPalindrome(std::string s) {
    int skipDistance = 0;
    for (int center = 0; center <= maxIndex(s); center++) {
      // Check if the radius has been filled
      if (m_radii[center] > 0) continue;
      findLongestRadius(s, center, skipDistance);
      skipDistance = fillRightHandSide(s, center);
    }
    return findLongestSubstring(s);
  }

 private:
  void findLongestRadius(const std::string &s, const int center,
                         const int skipDistance = 0) {
    m_radii[center] = 1;  // Self
    m_radii[center] += skipDistance;
    int left = center - 1 - skipDistance;
    int right = center + 1 + skipDistance;
    const int minLeft = 0;
    const int maxRight = maxIndex(s);
    while (left >= minLeft && right <= maxRight &&
           getChar(s, left) == getChar(s, right)) {
      m_radii[center]++;
      left--;
      right++;
    }
  }

  int fillRightHandSide(const std::string &s, const int center) {
    int skipDistance = 0;
    int left = center - 1;
    int right = center + 1;
    const int minLeft = leftBound(center, m_radii[center]);
    const int maxRight = rightBound(center, m_radii[center]);
    while (left >= minLeft && right <= maxRight) {
      const int radiusOnLeft = m_radii[left];
      const int maxRadiusOnRight = calcRadius(right, maxRight);
      if (radiusOnLeft < maxRadiusOnRight) {
        // Case 1
        m_radii[right] = radiusOnLeft;
      } else if (radiusOnLeft > maxRadiusOnRight) {
        // Case 2
        m_radii[right] = maxRadiusOnRight;
      } else {
        // Case 3: skip this distance for the next step 1
        skipDistance = maxRadiusOnRight - 1;
        break;
      }
      left--;
      right++;
    }
    return skipDistance;
  }

  std::string findLongestSubstring(const std::string &s) {
    // Find center index with the max radius
    int maxRadius = 0;
    int center = -1;
    for (int i = 0; i <= maxIndex(s); i++) {
      if (m_radii[i] > maxRadius) {
        maxRadius = m_radii[i];
        center = i;
      }
    }
    // Produce the palindrome
    std::string substr;
    for (int i = leftBound(center, maxRadius);
         i <= rightBound(center, maxRadius); i++) {
      if (i % 2 != 0) substr += getChar(s, i);
    }
    return substr;
  }

  char getChar(const std::string &s, const int index) {
    if (index < 0 || index > maxIndex(s)) return '\0';
    if (index % 2 == 0) return '|';
    const int realIndex = index / 2;
    return s.at(realIndex);
  }

  int maxIndex(const std::string &s) { return 2 * s.size(); }

  int calcRadius(const int from, const int to) {
    return std::abs(to - from) + 1;
  }

  int leftBound(const int index, const int radius) {
    return index - radius + 1;
  }

  int rightBound(const int index, const int radius) {
    return index + radius - 1;
  }

 private:
  int m_radii[2 * 1000 + 1] = {0};
};


上面的實作細節我還有額外的投影片在 GitHub 內，這邊為了簡潔我就不放上來了。

程式碼有點長? 沒錯，主要原因是因為我都沒 reuse 一些 variables，我把 Step 1 & Step 2 完全分開成兩個獨立的 functions 來做，這樣你可以看得很清楚唯一在下一個 while loop 被 reuse 的資訊只有 skipDistance。

我也把 index 和 radius 的計算規範成 maxIndex, calcRadius, leftBound, rightBound 這些 functions，那你在寫主邏輯的地方就不用再去多想是不是忘了 -1 還是 +1。

如果你要寫很短的程式碼當然也行，可是只要一個地方不小心弄錯，要 debug 起來可是很困難。

我就寧願寫看起來笨一點的程式碼，看得懂、好維護比較重要。

Submission 結果


又快又省記憶體，預料中的事。

更短的 Code

就是想要比較短的 code? 沒問題，我當然可以把上面的程式碼經過各種優化+簡化後可以變成底下這樣:


class Solution {
 public:
  std::string longestPalindrome(std::string s) {
    int radii[2 * 1000 + 1] = {0};
    int maxRad = 0, maxRadC = 0, maxRadRight = 1;
    for (int c = 0; c <= 2 * s.size(); c++) {
      if (radii[c] > 0) continue;
      radii[c] = maxRadRight;
      for (int l = c - radii[c]; nth(s, l) == nth(s, c + (c - l)); l--) {
        radii[c]++;
      }
      const int maxRight = c + radii[c] - 1;
      for (int l = c - 1; l >= c - radii[c] + 1; l--) {
        maxRadRight = maxRight - (c + (c - l)) + 1;
        if (radii[l] == maxRadRight) break;
        radii[c + (c - l)] = std::min(radii[l], maxRadRight);
      }
      if (radii[c] > maxRad) {
        maxRad = radii[c];
        maxRadC = c;
      }
    }
    return s.substr((maxRadC - maxRad + 1) / 2, (maxRad * 2 - 1) / 2);
  }

  char nth(const std::string &s, const int index) {
    if (index < 0) return '^';
    if (index > 2 * s.size()) return '$';
    if (index % 2 == 0) return '|';
    return s.at(index / 2);
  }
};


加上看過其他篇文章的 idea 後，這是從上面比較長的版本慢慢優化變成的，其中還加入了一些技巧:

  • 把 right 去掉，因為 center + (center - left) 就等於 right
  • 把 case 1 & case 2 合在一起，最後再處理 case 3
  • 可以觀察發現藍色對稱部分是最長的，中間的小對稱不可能比他長，所以我們提早檢查 radius 是不是最長的
  • 把 skipDistance 和 maxRadiusOnRight 合在一起，反正他們只差 1 而已
  • nth 讓前面和後面超出範圍的 index 回傳不一樣的字元，這樣我就不用檢查 left 和 right 的邊界，反正超出邊界一定會 nth(s, l) != nth(s, r)
  • 最後用會令人頭暈的 index 計算來直接算出 substring 應該從哪開始還有長度

經過了各種 Compiler Error, Wrong Answer 和各種 debugging 後的結果:


速度根本沒差，記憶體倒是省了 0.1 MB。值得嗎?

過了一分鐘再回頭看我已經看不懂了，不過變短的 code 還是有一個比大部分網路解答好的地方就是省記憶體，因為我沒有真的插入 ^ # $ 那些字元到 s。

參考資源

留言

發佈留言

此網誌的熱門文章

[試算表] 追蹤台股 Google Spreadsheet (未實現損益/已實現損益)

-
圖片
在 Dcard 上發了一篇文結果引起超多網友回應想要看試算表，我就來整理一下我追蹤台股用的 Google 試算表給大家。 這個試算表我目標是以 "簡單" 為主，底下我也會講解公式的運作原理，希望大家能以此試算表輕鬆擴充自己想要的功能。 功能 未實現損益 (Unrealized Gain/Loss 表) 不管同一支股票是不是有部分已經賣出，只要你還持有未賣出的股票這邊都看的到。 已實現損益 (Realized Profit/Loss 表) 我過去的績效如何? 在這個表一目了然。 未實現損益: 詳細資料 (Unrealized Stats 表) 我還持有多少股? 每股市值多少? 每股的成本是多少? 在這個表可以快速追蹤。 手機友善 (Mobile Friendly) 我為了在手機上也可以快速看我想看的資訊，把 "Unrealized Gain/Loss" 做成比較窄的版型。 只要下載 Google Sheets app 打開試算表就可以了。 Google Spreadsheet 連結 Google Drive 連結 Stock Tracking 使用方式 請先點 "檔案" -> "建立副本"，copy 一份試算表到你自己的 Google Drive 將 "Current Price" 表單中填上你想要追蹤的股票代號和名稱 將 "Transactions" 表單中刪除範例資料，但請務必留下第 2 列 (因為有公式)，然後慢慢往下填入你的資料 Step 1: 檔案 -> 建立副本 Step 2: 新增/刪除股票代號和名稱 (紅框圈起處)，灰色底欄位代表有公式 Step 3: 在 "Transactions" 表填入資料到白色底欄位 (紅框圈起處)，灰色底欄位代表要讓公式自動計算 未實現損益的正確算法 其實在發 Dcard 文之前我自己也像 另外一個表單 犯了同樣的錯誤，就是只有在股票全部賣光光 (持有 0 股) 後計算的未實現損益才會正確。還沒全部賣光怎麼辦? 難道就不顯示了嗎? 飲料的例子 只要股票中途賣出一部分，目前還持有部分股票的話，感覺計算就突然變得很複雜。但不用怕，我們來用飲料當作股票舉個超簡單的例子 (1 杯=1...
閱讀更多

[Side Project] 互動式教學神經網路反向傳播 Interactive Computational Graph

-
圖片
成品 互動式網頁連結:  Interactive Computational Graph 微積分課經典的範例 df/dx sin(x) / x: 2 個 inputs, 1 個 output, 沒有 hidden layer 的 fully connected neural network: 為何要做這套工具 以前在學 machine learning 的時候覺得最難理解的部分就是 backpropagation，也就是神經網路到底是怎麼用數學來做訓練的。 我們知道神經網路就是長這樣子: Source: Wikipedia 但實際上每個 neuron (圓圈圈) 裡面有許多基本的數學運算，像是 sum 還有 activation function: Source:  Neural Networks and Machine Learning 當我們把所有東西綜合在一起，腦袋就會打結，到底 chain rule 是怎麼在這麼複雜的神經網路之間套用的? 就算了解基礎也很難相信實際上到底怎麼運作的。我又沒有要真的使用的話，網路上的教學就覺得看看就好 Source:  A Step by Step Backpropagation Example 但決心要了解 backpropagation 細節之後，不少教學都提到了 computational graph，從基礎的數學運算當作 nodes 來去理解似乎是比較簡單的方式。 後來找到了這篇文章  Calculus on Computational Graphs: Backpropagation  把 chain rule 講解的簡單至極，於是就在想，為何我不做一個網頁，讓大家可以自由地組合想要的 graph，然後看一下 chain rule 是怎麼流通的。 失敗作經驗 在做這次 side project 前，其實早在一年前我就開始作另一個 side project 是想展現神經網路的訓練過程。名稱叫做 explain-derivatives，是被 TensorFlow 的一個網頁 A Neural Network Playground 啟發的。 但由於一開始欠缺規劃，想到什麼就加什麼功能進去，造成架構一直修改，最後由於程式碼架構太過複雜就放棄了。 這個 project 是用 Cy...
閱讀更多

[插件] 在 Chrome 網頁做區分大小寫的搜尋

-
圖片
寫軟體的時候最常用到的功能就是上網查 API 文件，但是常常會遇到一個困擾就是，搜尋的文字在 Chrome 裡面是不區分大小寫 (case-insensitive) 的。有的時候是還好，多按一些 F3 就找到了，可是有時候實在是太多大小寫的東西混在一起，這時候我們有一些快速的解法: 用 Firefox 搜尋 (Firefox 的搜尋框裡面預設就提供有 match case 的功能了) 開 DevTools 按 Ctrl + Shift + F 進行全部東西的搜尋 (不過大概會發瘋) 用插件的解法算是意外發現的，原本只是在找有沒有可以用 regex 搜尋的插件，沒想到意外發現  regex 的插件也是可以拿來做區分大小寫 (case-sensitive) 的一般搜尋。 用 Chrome Regex Search 來做區分大小寫的搜尋 先裝好 Chrome Regex Search 之後，按 Ctrl + Shift + F 或是點工具列的圖示，打上想找的文字就可以了。 例如我最近在看 Qt QTextCursor 的文件，但是我只想找 "cursor"，很不幸的如果用 Chrome 預設搜尋他會把一大堆 QText Cursor 也會找到: 如果用 Chrome Regex Search 就會侷限在小寫的 "cursor": 用 Regex 的陷阱 如果你不知道 regex 是什麼，那你很有可能會發現在搜尋一些含特殊符號的東西會搜尋到怪怪的東西，不然就是搜尋會失敗。 這是因為 regex 本來就是偏工程師在用的東西，有一些符號是有特殊涵意的，所以如果搜尋的字包含以下任何特殊符號記得要在前面加一個反斜線 \ ( ref ): . + * ? ^ $ ( ) [ ] { } | \ 例如我想搜尋 1+1=(2-1)+1*1 ，那其實要打 1\+1=\(2-1\)\+1\*1  才會正確找的到。 是不是很麻煩? 不過如果你要找的東西有特殊符號的話，其實用一般 Chrome 的搜尋通常是不會有太多搜尋結果的，那就用一般搜尋就好。 Chrome 什麼時候要支援大小寫搜尋? 其實上面弄了那麼麻煩，還不如開個 Firefox 搜尋更快。那我就滿好奇，這麼基本的功能怎麼 Chrome 一直都沒做? 找了一下才發現 Super User 有人...
閱讀更多