回分類題庫
d003: 99年台中區第三題
關鍵字: 99年台中區複賽

測資點 : 4 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 134 Times / 127 Users | Submit : 300 Times / 139 Users | Accepted rate : 91%
題目加入時間 : 2011-09-05 23:36

Content: 简体中文

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

Input:

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

Output:

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

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
baecad accbadcb
aca bddde
eeadec ebbbabc

Sample Output :

baecad accbadcb = acad
aca bddde = 0
eeadec ebbbabc = eac

Hint :

Author :

99年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum