a252: Another LCS
Tags : DP LCS
Accepted rate : 322人/348人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-09-22 11:46

Content

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

abccdda

        abcaddaacabda等都是它的子字串,但adcbddebddd等不是他的子字串。

        對於兩個字串accbbeffgfcebg,他們的LCS長度為 3,而LCScbgceg

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

Input

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

Output

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

Sample Input
abe
acb
babcd
Sample Output
2
測資資訊:
記憶體限制: 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 (文旋)
]


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