d231: 97北縣賽-2-基因序列密碼問題

出處 http://zerojudge.tw/ShowProblem?problemid=d231

內容 ：

2.基因序列密碼問題

基因序列是由四個鹼基A、C、G、T組合而成，例如 AGTTACGGGTTCGTAA有可能是某個基因序列。在生物學裡常見的問題是要找出兩的基因序列的最長共同子序列

(Longest Common Subsequence)，例如 AGTTACGGGTTCGTAA 和 GTCGGAAG 的最長共同子序列是GTCGGAA。請注意 subsequence和 substring 不同，subsequence的字母不需要在原來字串裡鄰近出現，只需要保持字母的順序。你的任務就是要寫一個程式找出兩個基因列序的最長共同子序列。假設每一對基因列序最多只有一個最長共同子序列。

輸入說明 ：

條件限制

基因序列長度為整數，1≤基因序列長度≤50

輸入格式

第一行是第一個基因序列，1≤基因序列長度≤50。

第二行是第二個基因序列，1≤基因序列長度≤50。

輸出說明 ：

輸出格式

請由螢幕印出第一個和第二個基因序列的最長共同子序列，如果沒有最長共同子序列就輸出字母E。

範例輸入 ：

AAAG

GAG

範例輸出 ：

AG

提示 ：

出處 ：

北縣縣賽 (管理：nanj0178)

解題策略

LCS，需重建最佳解