Q: http://uva.onlinejudge.org/external/109/10949.html

 

繼 UVA 10030, UVA 10807 之後

又一個在網路上毫無詳解的題目

 

這題乍看之下很簡單,就只要求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的長度

最後將長度相減,即可得到答案

 

 

這題寫到最後有點沒耐心了

所以也不強求速度了

有過就好 

 

arrow
arrow
    文章標籤
    ACM UVA 程式 DP
    全站熱搜

    Tube 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄