d231. 97北縣賽-2-基因序列密碼問題
Tags : DP
Accepted rate : 503人/563人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-04-27 19:05

Content

2.基因序列密碼問題

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

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

Input
條件限制
   基因序列長度為整數,1≤基因序列長度≤50輸入格式
   第一行是第一個基因序列,1≤基因序列長度≤50。   第二行是第二個基因序列,1≤基因序列長度≤50。
Output
輸出格式
請由螢幕印出第一個和第二個基因序列的最長共同子序列,如果沒有最長共同子序列就輸出字母E。
Sample Input #1
AAAG
GAG

Sample Output #1
AG
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
DP
出處:
97學年度北基區資訊學科能力競賽 [管理者: nanj0178 (nanj) ]

Status Forum 排行

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