e031. 6. 串聯重複 - 高中生程式解題系統

內容

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

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

輸入說明

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

輸出說明

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

範例輸入 #1

輸入範例 1：
8
aabababa

輸入範例 2：
12
aaabaaabaaab

輸入範例 3：
11
abacabcacba

範例輸出 #1

輸出範例 1：
ab
3

輸出範例 2：
aaab
3

輸出範例 3：
abacabcacba
1

測資資訊：

記憶體限制： 512 MB

提示：

本題共有3個子題，每一子題有多筆測資：

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

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

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

標籤:

出處:

107學年度全國資訊學科能力競賽 [管理者： icube (!@#$%^&*()_...) ]

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