c008: Ⅷ. 字串大搜尋
Tags : DP LCS
Accepted rate : 5人/6人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-11-19 21:32

Content

給予由字母 a, b, c, d, e 所組成之兩個字串 S1S2,我們可以找出其最長的相同子順序字串 (Longest Common Subsequence)。所謂相同子順序字串在原始字串中並不一定連續。 例如,ba, ad, cad, acad 均為字串 S1 = baecadS2 = accbadcb 之相同子順序字串;而則其最長的相同子順序字串為 acad。請設計一程式讀取三列資料,每一列包括兩個字串(以空白分隔),兩個字串皆是由字母 a, b, c, d, e 所組成,每個字串長度皆不會超過 20 個。請針對每一列的兩個字串輸出其最長的相同子順序字串 (Longest Common Subsequence),若是沒有相同子順序字串則輸出 0;若有多個相同長度的最長子順序字串,請輸出其中一個。

 
Input

輸入資料總共有三列,每一列包括兩個字串(以空白分隔)。

字串長度 ≤ 20

Output

請依照輸出範例的格式,輸出兩個字串及其最長的相同子順序字串。

Sample Input
baecad accbadcb
aca bddde
eeadec ebbbabc
Sample Output
baecad accbadcb = acad
aca bddde = 0
eeadec ebbbabc = eac
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (25%): 1.0s , <1K
不公開 測資點#1 (25%): 1.0s , <1K
不公開 測資點#2 (25%): 1.0s , <1K
不公開 測資點#3 (25%): 1.0s , <1K
Hint :
在民國 99 年時,台中複賽竟然還沒使用 Online Judge,測資也超弱只有兩個,放上來給大家笑一笑秒殺 der。
Tags:
DP LCS
出處:
99 年台中區第三題 [管理者:
nevikw39 ($\mathscr{nevikw}\pmb{39}\in\mathbf{37}^{th}$)
]


ID User Problem Subject Hit Post Date
10
nevikw39 ($\mathscr{nevikw}\pmb{39}\in\mathbf{37}^{th}$)
c008
字串大搜尋:LCS
120 2020-06-14 23:10