操作名称：删除、插入、替换
    编辑距离：编辑操作的数量

    将单词kittchen通过编辑操作变成sitting
    方案一：kittchen-sittchen-sitthen-sitten-sittn-sittin-sitting<编辑六次：编辑距离为6>
    方案二：kittchen-sittchen-sitthen-sitten-sittin-sitting<编辑距离5>

    问题描述：Minimum Edit Distance,MED
    输入：
    长度为n的字符串，长度为m的字符串t
    输出：
    求出一组编辑操作O=零|O|最小，s经过O操作使得s=t

    image.png
    image.png
    image.pngimage.png

    1. #include<iostream>
    2. using namespace std;
    3. /*
    4.     操作名称：删除、插入、替换
    5.     编辑距离：编辑操作的数量
    7.     将单词kittchen通过编辑操作变成sitting
    8.     方案一：kittchen-sittchen-sitthen-sitten-sittn-sittin-sitting<编辑六次：编辑距离为6>
    9.     方案二：kittchen-sittchen-sitthen-sitten-sittin-sitting<编辑距离5>
    11.     问题描述：Minimum Edit Distance,MED
    12.     输入：
    13.     长度为n的字符串，长度为m的字符串t
    14.     输出：
    15.     求出一组编辑操作O=<e1,e2,e3.....en>零|O|最小，s经过O操作使得s=t
    17. */
    18. void Print_MED(char Rec[][7],char s[],char t[], int i, int j) {
    19.     if (i == 0 && j == 0)
    20.         return;
    21.     if (Rec[i][j] == 'LU') {
    22.         Print_MED(Rec, s, t, i - 1, j - 1);
    23.         if (s[i] == t[j])
    24.             cout << "无需操作！" << endl;
    25.         else
    26.             cout << "用t[" << j << "]替换s[" << i << "]\n";
    27.     }
    28.     else if (Rec[i][j] == 'U') {
    29.         Print_MED(Rec, s, t, i - 1, j);
    30.         cout << "删除s[" << i << "]\n";
    31.     }
    32.     else {
    33.         Print_MED(Rec, s, t, i , j- 1);
    34.         cout << "插入t[" << j << "]\n";
    35.     }    
    36. }
    38. int main() {
    39.     char s[] = "OABCBDAB", t[] = "OBDCABA";
    40.     const int n = 7, m = 6;
    42.     int Dp[n+1][m+1] = {};
    43.     char Rec[n+1][m+1];
    45.     //init
    46.     for (int i = 0; i <= n; i++) {
    47.         Dp[i][0] = i;
    48.         Rec[i][0] = 'U';
    49.     }
    50.     for (int i = 0; i <= m; i++) {
    51.         Dp[0][i] = i;
    52.         Rec[0][i] = 'L';
    53.     }
    54.     int c;
    55.     //动态规划
    56.     for (int i = 1; i <= n; i++){
    57.         for (int j = 1; j <= m; j++) {
    58.              c = 0;
    59.             if (s[i] != t[j])
    60.                 c = 1;                //辅助替换
    62.             int Replace = Dp[i - 1][j - 1] + c;    //替换
    63.             int Delete = Dp[i - 1][j] + 1;        //删除
    64.             int Insert = Dp[i][j - 1] + 1;        //插入
    66.             int min = Replace;
    67.             min = min < Delete ? min : Delete;
    68.             min = min < Insert ? min : Insert;
    70.             if (min== Replace) {
    71.                 Dp[i][j] = Replace;                //根据递推公式构造Dp数组
    72.                 Rec[i][j] = 'LU';
    74.             }
    75.             else if (min == Delete) {
    76.                 Dp[i][j] = Delete;
    77.                 Rec[i][j] = 'U';
    78.             }
    79.             else {
    80.                 Dp[i][j] = Insert;
    81.                 Rec[i][j] = 'L';
    82.             }
    83.         }
    84.     }
    86.     for (int i = 0; i <= n; i++) {
    87.         for (int j = 0; j <= m; j++)
    88.             cout << Dp[i][j] << " ";
    89.         cout << endl;
    91.     }
    92.     cout << endl << "最短编辑距离为：" << Dp[n][m] << endl;
    94.     //追踪最优方案：(还有问题)
    95.     //Print_MED(Rec, s, t, n, m);
    97. }