e031: 6. 串聯重複
標籤 :
通過比率 : 3人/5人 ( 60% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-01-25 15:56

內容

DNA序列中,有時某個片段會連續重複出現數十次,甚至數千次以上,這些重複出現的片段(簡稱重複片段),扮演著重要的生理角色,也與一些遺傳疾病相關,這種現象被統稱為串聯重複。串聯重複常被用來描述遺傳特徵,可應用在檢定親子關係與一些遺傳疾病,例如說遺傳性非息肉病性結直腸癌,主要與長度為2的AC重複片段有關;肌肉萎縮症則與長度為3的CTG重複片段有關。在遺傳學中,長度介於10到60的重複片段稱為小衛星(minisatellite),長度小於10的則稱做微衛星(microsatellite)。

在本問題中,我們想找出連續出現次數最多的那些重複片段及其次數。若字串y可表示成uxkv,其中u、x、v為字串(u或v可以是空字串,但x不行)且k為大於等於1的整數,則我們稱重複片段x連續出現k次。例如令u=a、x=bc、k=3、v=d,則y=ux3v=uxxxv=abcbcbcd,也就是說重複片段bc在y裡連續出現3次。又如在y=aaaaaa中,雖然重複片段aa連續出現3次,但重複片段a卻連續出現6次,因此我們會選擇a而不選擇aa做為解答。為了確保輸出唯一,假設同時有好幾組解,請輸出重複片段x較長的那組,若這樣還是有好幾組解,則輸出重複片段字典序最小的那組。

輸入說明

每筆測資共有2行,第1行為正整數n,第2行為n個小寫英文字母所組成之字串。

輸出說明

針對每筆測資,第1行輸出所求之重複片段,第2行輸出其連續出現次數。

範例輸入
輸入範例 1:
8
aabababa

輸入範例 2:
12
aaabaaabaaab

輸入範例 3:
11
abacabcacba
範例輸出
輸出範例 1:
ab
3

輸出範例 2:
aaab
3

輸出範例 3:
abacabcacba
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (6%): 2.0s , <1K
公開 測資點#1 (1%): 2.0s , <1K
公開 測資點#2 (1%): 2.0s , <1K
公開 測資點#3 (1%): 2.0s , <1K
公開 測資點#4 (1%): 2.0s , <1K
公開 測資點#5 (1%): 2.0s , <1K
公開 測資點#6 (24%): 2.0s , <1K
公開 測資點#7 (1%): 2.0s , <1K
公開 測資點#8 (1%): 2.0s , <1K
公開 測資點#9 (1%): 2.0s , <1K
公開 測資點#10 (1%): 2.0s , <1K
公開 測資點#11 (1%): 2.0s , <1K
公開 測資點#12 (54%): 2.0s , <1M
公開 測資點#13 (1%): 2.0s , <1M
公開 測資點#14 (1%): 2.0s , <1M
公開 測資點#15 (1%): 2.0s , <1M
公開 測資點#16 (1%): 2.0s , <1M
公開 測資點#17 (1%): 2.0s , <1M
公開 測資點#18 (1%): 2.0s , <1M
提示 :

本題共有3個子題,每一子題有多筆測資:

第1子題,輸入字串長度小於100,全部解出可得11分;

第2子題,輸入字串長度小於1000,全部解出可得29分;

第3子題,輸入字串長度小於10000個字元,全部解出可得60分。

標籤:
出處:
107學年度全國資訊學科能力競賽 [編輯:
icube (輸光光)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」