a252. Another LCS - 高中生程式解題系統

Content

一般LCS問題( Longest Common subsequence, 最長共同子字串)就是給定兩個字串，求出他們的LCS。為了理解這裡子字串定義，舉例來說，對於字串

abccdda

abc、adda、aca、bda等都是它的子字串，但adc、bdde、bddd等不是他的子字串。

對於兩個字串accbbeffg、fcebg，他們的LCS長度為 3，而LCS為cbg或ceg。

現在我們把問題弄得難一點，給三個字串，請求出他們的LCS長度為多少？

Input

每個測資檔僅包含一筆測資，每筆測資有三個字串。測資保證三個字串的長度都不超過100，而且字串皆由小寫字母組成。

Output

對每筆測資，輸出LCS的長度。

Sample Input #1

abe
acb
babcd

Sample Output #1

測資資訊：

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

Hint ：

Tags:

DP LCS

出處:

2011 成功高中校內賽初賽第三題 [管理者： david942j(文旋) ]