[UVA] 164 String Computer

這個題目分成兩部份：第一部份，求兩個字串的minimum editing distance (即 Levenshtein Distance)，第二部份，求出step by step的edit 指令。

第一部份算是DP的老套了，蓋個二維DP table dp[i][j] 即可，i 為source string, j 為target string.。詳見wiki。

第二部份還蠻有意思，搞了我快三個小時。第一步是在建DP時要記住backtrace的path，然後拫據back trace的方向決定instruction的種類(-> 是back edge, 從終點返回起點)

  dp [i ] [ j]    ->    dp [ i - 1] [ j  - 1]   // CHANGE
                     ->    dp [ i ] [ j - 1 ]       //  INSERT
                     ->    dp [ i - 1 ] [ j ]       //  DELETE

第二步是決定instruction的值，包含char 與 position,
for dp [ i ] [ j ]:
                           char
  CHANGE:    target[ j - 1]
  INSERT        target[ j - 1]
  DELETE       source[ i - 1]

position是我認為這題最tricky的部份。由於instruction 會改變source string的長度，所以對dp[i][j]來說，editing position不會剛好在 i, 而是i + 字串長度累積變化量 (假設叫 delta) 。所以在建dp table時要同時紀錄每個cell的字串長度累積變化。


                           position
  CHANGE:    i + delta
  INSERT        i + delta + 1 (!)
  DELETE       i + delta