b397: 找出最長共同子序列
Tags : LCS 回溯
Accepted rate : 49人/72人 ( 68% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-09-15 14:40

Content

給兩個字串 A, B,按照字典順序列出 A, B 的最長共同子序列。

Input

第一行會有一個整數 T,表示接下來會有 T 組測資。每一組測資會有兩行,每一行上有兩個字串 A, B。

所有字串長度 L (1 <= L <= 32),且只由小寫字母和數字構成。

Output

對於每一組測資,第一行輸出有多少不同的最長共同子序列,接著每一行按照字典順序輸出的 A B 的最長共同子序列。

Sample Input #1
3

abcabcaa
acbacba

abcdfgh
abccfdsg

3124158592654359
3173415926581359
Sample Output #1
Case #1: 7
ababa
abaca
abcba
acaba
acaca
acbaa
acbca
Case #2: 2
abcdg
abcfg
Case #3: 1
314159265359
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (30%): 1.0s , <1M
公開 測資點#5 (30%): 1.0s , <1K
Hint :

每一組測資不同的最長共同子序列不超過 100000 個。

測資有錯或者題目重複歡迎來信告知。

Tags:
LCS 回溯
出處:
妮可 [管理者:
morris1028 (碼畜)
]


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