Q: http://uva.onlinejudge.org/external/109/10949.html
又一個在網路上毫無詳解的題目
這題乍看之下很簡單,就只要求LCS的長度之後
再用字串一和字串二的長度去扣掉LCS的長度即可
問題是這題的字串長度給到20000
用O(n^2)的LCS解法會TLE
在網路上找了好久之後終於找到演算法筆記裡的介紹:
Longest Common Subsequence: Hunt-Szymanski Algorithm
這個演算法是先把 LCS 問題看成二維 LIS 問題
再把二維 LIS 問題轉成一維 LIS 問題
然後用 Robinson-Schensted-Knuth Algorithm 來算 LIS
得到的長度即為LCS的長度
可有效減少計算複雜度
輸入的時候要小心不要把不相關的字元也讀進去了
根據題目要求建立好兩個字串之後
先判斷字串長度, 再丟進函式計算LCS的長度
最後將長度相減,即可得到答案
這題寫到最後有點沒耐心了
所以也不強求速度了
有過就好
文章標籤
全站熱搜
留言列表
生活點滴 (3)
