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

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

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
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 (文旋) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
42991 toseanlin@gm ... (Dr. SeanXD) a252
C++詳解
134 2024-10-14 21:37
38690 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) a252
__思路
302 2023-12-17 16:35
28326 alison.acorn ... (aa w) a252
三維 LCS
994 2021-11-29 10:32
26212 s0975247623@ ... (愛吃又愛睡的Weber) a252
C++淺見
1130 2021-07-24 12:01