d076. P_6_7 LCS 最長共同子序列

Content

Longest Common Subsequence(LCS) 是序列分析的重要問題，一個序列的子序列是指將其中某些元素刪除後所得到的序列，字串可以看成字母組成的序列，以 ”algorithm” 為例， ”algtm” 與 ”lgh” 都是它的子序列，但是” agl” 則不是，因為你不可以調整位置重新排列。輸入兩序列，LCS要找一個最長的序列，它是兩輸入序列的共同子序列。LCS可以是一種作為字串相似度的定義，有很多重要的應用。

輸入兩字串，計算其 LCS 的長度。

Input

第一行與第二行個有一個字串，字串均只含小寫字母，長度不超過 500。

Output

LCS 長度。

Sample Input #1

algorithm
alignment

Sample Output #1

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (16%): 1.0s , <1K
公開測資點#1 (16%): 1.0s , <1K
公開測資點#2 (17%): 1.0s , <1K
公開測資點#3 (17%): 1.0s , <1K
公開測資點#4 (17%): 1.0s , <1K
公開測資點#5 (17%): 1.0s , <1K

Hint ：

Tags:

ch6

出處:

Prof. Wu [管理者： ktlai (K．我已霸榜．Tlai) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」