UVa526 - String Distance and Transform Process (Minimum Edit Distance 詳解)

題目大意：

給你兩個字串分別是 A,B 你可以用插入、刪除、替換，來將 A 字串轉換成為 B 字串，輸出需要幾次的轉換，也要將步驟輸出。

這題很毒瘤，A,B 都必須用 getline 實作，字串可以包括空白

分析：

這題為教學題，但此問題還有一點點的小設計，需要稍加解釋才能完全理解。
這題要用到最短修改距離 Minimum Edit Distance，這是一個動態規劃，遞迴式如下。

Minimum Edit Distance 介紹

可以透過刪除、插入、替換字元來達到將 A 字串轉換到 B 字串，並且是最少編輯次數。
此演算法的時間複雜度 \(O(n^2)\)

最短修改距離 Minimum Edit Distance 應用

• DNA 分析
• 拼寫檢查
• 語音辨識
• 抄襲偵測

MED 實現與說明

由於 MED 此演算法是動態規劃原理的部分我個人認為沒有很難，因此沒有說明原理。其實是作者很早以前就會了所以不想花時間寫XD

int dis[MAXN][MAXN]; 
//dis[A][B] 指在 strA 長度 0 to A 與 strB 長度 0 to B 的最短修改距離為多少
//這裡假設由 A 轉換 B
string strA , strB ;
int n , m ;
n=strA.length() ;
m=strB.length() ;

int med(){ //Minimum Edit Distance
    for(int i = 0 ; i <= n ; i++) dis[i][0] = i ;
    // 由於 B 是 0 ，所以 A 轉換成 B 時每個字元都要被進行刪除的動作
    for(int j = 0 ; j <= m ; j++) dis[0][j] = j ;
    // 由於 A 是 0 ，所以 A 轉換成 B 時每個字元都需要進行插入的動作
    for(int i = 1 ; i <= n ; i++){ // 對 strA 每個字元掃描
        for(int j = 1 ; j <= m ; j++){ // 對 strB 每個字元進行掃描
            if(strA[i-1] == strB[j-1]) dis[i][j] = dis[i-1][j-1] ;
            // 如果他們字元相同則代表不需要修改，因此修改距離直接延續先前
            else dis[i][j] = min(dis[i-1][j-1], min(dis[i-1][j] , dis[i][j-1]))+1;
            // 因為她們字元不相同，所以要詢問 replace , delete , insert 哪一個編輯距離
            // 最小，就選擇他 +1 來成為目前的最少編輯距離
        }
    }
}

return dis[n][m] ; // 這就是最少編輯距離的答案

QUESTION: 現在的我們知道最少編輯距離的答案，那我們可以回推有哪些字元被編輯嗎？

那當然是可以的阿XD，只是寫起來比較麻煩。通常這種答案會有很多種，依照題目的要求通常只需要你輸出一種方式即可。除非是毒瘤

實現方式如下：

由於這回推其實也就只是一個簡單的遞迴你能夠推得出 DP 就可以知道要怎麼回推哪些字元被編輯，於是我就在程式碼上旁寫下說明來幫助讀者閱讀。希望能夠幫助到

int cnt = 0 ;
void backtracking(int i , int j ){
    if(i==0 || j==0){  //表示 A or B 完全沒有字串
        while( i > 0 ){ 
            // 由於 B 完全沒有字串，所以需要刪除 A 的所有字串
            cout << cnt++ << " Delete " << i << '\n' ;
            i--;
        }
        while( j > 0){
            // 由於 A 完全沒有字串，所以需要增加 B 的所有字串
            cout << cnt++ << " Insert " << i+1 << "," << strB[j-1] << '\n' ;
            j-- ;
        }
        return ;
    }

    // 如果字元相等代表這裡沒有增加修改距離
    // 特別注意：不可以使用　dis[i][j] == dis[i-1][j-1]
    // 有可能 dis[i-1][j]+1 = dis[i-1][j-1] 這樣就會導致 strB 的第 j 字元遺失
    // 而讓回推出錯
    if(strA[i-1] == strB[j-1])
        backtracking(i-1,j-1); // 往前推
    else{
        if(dis[i][j] == dis[i-1][j-1]+1){ // 這次是使用替換指令
            cout << cnt++ << " Replace " << i << "," << strB[j-1] << '\n' ;
            backtracking(i-1,j-1); // 回推替換
        }
        // 特別注意這裡要使用 else if ，不可以只有 if，這樣會讓回推變成 BFS 而不是 DFS
        // 答案就會變成輸出所有的替換可能而不是輸出一種「完整」的其中一種回推
        else if(dis[i][j] == dis[i-1][j]+1){  // 這次是使用刪除指令
            cout << cnt++ << " Delete " << i << '\n' ;
            backtracking(i-1,j) ; // 回推刪除
        }
        else if(dis[i][j] == dis[i][j-1]+1){ // 這次是使用插入指令
            cout << cnt++ << " Insert " << i+1 << "," << strB[j-1] <<'\n'  ;
            backtracking(i,j-1); // 回推插入
        }
    }
}

焦點回到題目上，解開題目的小設計

甚麼，這題好像沒有甚麼焦點！

還是有的，這題的輸入不一定要用字串，只要是那一行都可以，所以請記住要用getline，不要像我這個大笨蛋一直用cin >> strA >> strB，然後一直找不出答案，還在想是不是自己 DP 寫不好

參考連結

Uva 526 - String Distance and Transform Process
萊文斯坦距離

心得

其實這演算法在我高中時就有學習過了，但是我高中的時候不懂得整理資料的重要性。讓我在高中學會的很多演算法一經過時間的摧殘就忘記這些演算法是甚麼了，可惡，應該高中就要學會整理資料的能力，這太重要了。

然後在此奉戒各位女朋友可以教，但是不要讓她影響到你的正業，我常常會因為女朋友而影響正業導致高三下的時候荒廢了我的程式，因為已經知道自己能保送上某間大學而每天跟女朋友打打鬧鬧，到最後跟女朋友分手還不是甚麼都沒有獲得。

不過如果你能跟她在一起到結婚的話，就當我沒說吧！這也是令我羨慕的結局，我也好想要。

謝謝新北市教育局能讓我在高三寒假時去板橋高中訓練程式設計，讓我可以增強我的演算法能力，也謝謝板橋高中的蝸牛老師，你的指導能力讓我在學習演算法的路上突飛猛進。老師您真的教得很好，高中沒有你真的沒辦法像現在這樣。

題目程式碼

其實就是沒有附上說明的程式碼，我也花了兩個小時撰寫文章，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋。希望可以幫助到各位。

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

於是這裡就補述一些題目給的資料範圍限制與標頭檔了。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 100
using namespace std;
string strA , strB ;
int dis[MAXN][MAXN] , back_table[MAXN][MAXN] ;
int cnt , m , n  ;

void backtracking(int i , int j ){
    if(i==0 || j==0){
        while( i > 0 ){
            cout << cnt++ << " Delete " << i << '\n' ;
            i--;
        }
        while( j > 0){
            cout << cnt++ << " Insert " << i+1 << "," << strB[j-1] << '\n' ;
            j-- ;
        }
        return ;
    }

    if(strA[i-1] == strB[j-1])
        backtracking(i-1,j-1);
    else{
        if(dis[i][j] == dis[i-1][j-1]+1){
            cout << cnt++ << " Replace " << i << "," << strB[j-1] << '\n' ;
            backtracking(i-1,j-1);
        }
        else if(dis[i][j] == dis[i-1][j]+1){
            cout << cnt++ << " Delete " << i << '\n' ;
            backtracking(i-1,j) ;
        }
        else if(dis[i][j] == dis[i][j-1]+1){
            cout << cnt++ << " Insert " << i+1 << "," << strB[j-1] <<'\n'  ;
            backtracking(i,j-1);
        }

    }

}

void med(){ //Minimum Edit Distance
    for(int i = 0 ; i <= n ; i++) dis[i][0] = i ;
    for(int j = 0 ; j <= m ; j++) dis[0][j] = j ;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            if(strA[i-1] == strB[j-1]) dis[i][j] = dis[i-1][j-1] ;
            else dis[i][j] = min(dis[i-1][j-1], min(dis[i-1][j] , dis[i][j-1]))+1;
        }
    }
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout);
#endif // LOCAL
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int flag = 0 ;
    while(getline(cin ,strA) && getline(cin , strB)){
        n=strA.length() ;
        m=strB.length() ;
        cnt = 1 ;
        med();
        if(flag) cout << '\n' ;
        flag = 1 ;
        cout << dis[n][m] << '\n' ;
        backtracking(n,m);
    }
    return 0;
}