y19m10_a3猴子打字遊戲 (Typing) 2019年10月TOI練習賽 潛力組 {題目連結}

問題敘述

聽過無限猴子定理嗎？此定理說讓一隻猴子在打字機上隨機按鍵，當按鍵數 達到無窮時，幾乎必然能夠打出任何給定的文字。有三個養猴人，他們聽說這個 理論以後，決定辦一個比賽，內容如下： 首先，他們共同決定一段目標文字。然後，每個人各自帶一隻自己養的猴子 坐上打字機，並給予相同時間打字。最後，比賽看誰的猴子打出的文字與目標文 字的最佳編輯距離最小。 編輯距離定義如下：要將字串 y 變成字串 x，可對 y 進行新增、刪除、取 代；其中，新增及刪除一個字元的編輯距離定為 2，取代一個字元的編輯距離定 為 3。舉例來說，將字串 bcde 變成字串 abcc 可以有至少下列兩種不同做法：

上例中，我們稱符號 - 為 gap。第一列有 gap 表示要對第二個字串進行刪除，第 二列有 gap 表示要對第二個字串進行新增；若兩列的字母不同，表示要將第二列 的字串取代為第一列的。以上三種情況都會增加編輯距離，若對應到相同字元則 不會。第一種作法的編輯距離為 7 (2+3+2)，而第二種作法的編輯距離為 11 (2+2+3+2+2)。第一種作法為所有作法中，編輯距離最小的作法，因此將字串 bcde 變成字串 abcc 的最佳編輯距離為 7。

評分說明 此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資 料才能獲得該組分數。L 為字串長度。

第一組 (30 分) : 1<=L<=10。

第二組 (70 分) : 1<=L<=10^4。