20000. Longest Common Subsequence (Design Strategies for Computer Algorithms)

I'm a slow walker, but I never walk backwards.

輸入格式

總共有五組測資,各佔10 分。每組測資包含兩個字串。每個字串長度不超過 100,且都是由英文字母組成。

輸出格式

對於每組測資,第一行請輸出兩個數字,分別代表最長共同子序列的長度和個數,下一行開始請將所有的最長共同子序列依字典順序排序後輸出,每個子序列各佔一行。注意答案中可能包含相同的子序列,因為同一個子序列在兩個輸入字串中的位置可能不同。

範例輸入 1

PUWBVNUCUUESSJUNSVHE
CIHSIIDWCSUTOSWJHTOB

範例輸出 1

6 8
CSSUSH
WCSSJH
WCSUSH
WCSUSH
WCUSJH
WCUSJH
WCUSJH
WCUSJH

範例輸入 2

QHCCDETMFPPWZGIFEFUA
GZXPAWWOOCZEMBIPHECM

範例輸出 2

5 10
CEMIE
CEMIE
CEMPE
CEMPE
CEMPE
CEMPE
PWZIE
PWZIE
PWZIE
PWZIE

Discussion