參考 題型範例 - 全國高級中等學校技藝競賽平台 工業類 112-2
本地下載題目(dbf) 題目:最小編輯距離
問題描述
說明:
    讀入兩個英文字(word),印出由第一個英文字轉換成第二個英文字所需要的最小編輯距離
(edit distance)。編輯距離包括三種動作的成本:插入(insert)字母、刪除(delete)
字母、及取代(substitute)字母。例如輸入兩個英文字"idea"及"deal",如果刪除"idea"
中的第一個字母 "i",並在最後面插入字母 "l",就可以將 "idea" 轉換成 "deal"。
再舉一個例子,如果輸入的兩個英文字是"but"及"bait",我們先將第一個字中的字母"u"
取代成字母"a",然後再在字母"a"之後插入字母"i",就可以將"but"轉換成"bait"。
當插入及刪除動作的成本都是 1,取代動作的成本是 2,則第一個例子將 "idea"轉換成
"deal"的編輯距離就是 2 (包括一個刪除及一個插入);而第二個例子將"but"轉換成"bait"
的編輯距離就是 3 (包括一個取代及一個插入)。由於兩個英文字間可能有多種轉換方法,且
每一種轉換方法都有它的編輯距離,而我們要找出的就是兩個英文字間的最小編輯距離。
這個問題可以用 dynamic programming 的方法來解。我們定義 D(i,j)為由第一個英文字
X 的前 i 個字母轉換到第二個英文字 Y 的前 j 個字母的最小編輯距離;若 X 有 n 個字母
且 Y 有 m 個字母,則由 X 轉換成 Y 的最小編輯距離就是 D(n,m)。D(i,j)可以用下列方式計:



以下是上面第一個例子的計算結果,其中最右下角的數值 2 就是這個例子的最小編輯距離: 
X
Y
deal
01234
i12345
d21234
e32123
a43212
另外,在 Visual Basic 中取得字串變數 X 的字母的方法是 X.Chars(i),而在 C++ 及
C#中中取得字串變數 X 的字母的方法是 X[i]。
輸入格式輸出格式
第一列輸入第一個英文字,
第二列輸入第二個英文字,
每個英文字不超過 20 個字母,不考慮輸入錯誤的情形。
印出由第一個英文字轉換成第二個英文字所需要的最小編輯距離。

範例一
輸入正確輸出
idea
deal
2

執行結果


範例二
輸入正確輸出
but
bait
3

執行結果


範例三
輸入正確輸出
abcde
xyz
8

執行結果


範例四
輸入正確輸出
aXbZY
XYZ
4

執行結果

程式碼下載