b954: 你的生物有學好嗎?
Tags :
Accepted rate : 4人/6人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-01-28 11:48

Content

基因序列是由四個鹼基A、C、G、T 組合而成,使用一串字母表示的真實的
或者假設的攜帶基因信息的DNA 分子的一級結構。每個字母代表一種核鹼基,兩
個鹼基形成一個鹼基對,鹼基對的配對規律是固定的。例如 AGTTACGGGTTCGTAA
有可能是某個基因序列目前。在生物學裡常見的問題是要找出兩的基因序列的最
長共同基因序列,因為生物科技中最重要的就是基因重組,在做基因重組時,需
要用到限制酶來剪下一段完全相同的基因序列,因此若能找出越長的共同基因序
列,就能修改越多的基因。
今天科學家發現了一個奇特的外星生物,他的DNA 組合有很多種(包含大小
寫英文以及數字)。你的任務就是要寫一個程式找出多個基因列序的最長共同基
因序列。

Input

每筆測資中,第一行有一個正整數n(n=2或3),接下來有n行不含空白的字串,分別代表n個基因序列。

所有測資符合每個基因序列長度不超過3500個基因,且每筆測資中所有字串長度乘積不超過35000000。

Output

對於每筆測資,請輸出1行為這n個基因序列的最長共同基因序列。

Sample Input
2
aa2cbADAcB1d
a2cAAcBd1bAD
2
bD2A33CaabB1Bd
A11Bd3bddcBBa
3
Bd1b3a1bDD1CCb
Abcb13b3abDa1bDDc
bA33d2cbaa12db3a1bDac
Sample Output
3
3
4
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
出處:
105學年度復旦程式設計班檢定考 [管理者: ]


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