TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

61.9% (13/21)

Submission's AC Ratio

15.5% (36/233)

Description

迪亞哥是某國家最高情報機構安插至某恐怖組織的臥底探員,負責進行滲透工作,以獲取最新恐怖活動的各項情報,協助各項反恐行動的遂行。為了避免臥底的身份曝光,迪亞哥與上級對口單位的所有聯絡事宜,皆必須經過特殊的演算法進行加密;同時,為了避免加密的內容遭到破解,迪亞哥每天都會使用不同的加密密鑰(encryption key),並且利用智慧手機的即時通訊軟體,將當日的加密密鑰編碼後傳送給上級對口單位。
為了解碼迪亞哥所傳送的各項珍貴情報,上級單位必須首先解碼找出當日的加密密鑰,接著才能使用該密鑰進行解密。你的任務便是協助上級單位從迪亞哥傳送的即時通訊內容中,尋找出當日的加密密鑰。已知迪亞哥所傳送的訊息為一個前k 個小寫的英文字母所組成的字串,且該字串的長度為n。該字串中含有至少一個出現次數為兩次(含)以上的子字串,而其中長度最長的子字串即為當日的加密密鑰。

Input Format

輸入為一個長度為 n 且由前 k 個小寫英文字母所組成的字串。

Output Format

請輸出該組測資中的加密密鑰。註:每一筆測試資料皆恰只有一組唯一解。

Sample Input

輸入範例一
abacab

輸入範例二
abababab

Sample Output

輸出範例一
ab

輸出範例二
ababab

Hints

本題共有5 組測試資料,每組20 分:
第一組測試資料中,1< n ≤ 10,k = 2。
第二組測試資料中,1 < n ≤ 50,2 ≤ k ≤ 5。
第三組測試資料中,1 < n ≤ 100,2 ≤ k ≤ 10。
第四組測試資料中,1 < n ≤ 1000,2 ≤ k ≤ 10。
第五組測試資料中,1 < n ≤ 100000,2 ≤ k ≤ 10。

Problem Source

臺北市103 學年度高級中學資訊學科能力競賽程式設計試題第五題
Set by Paupière
若測資有誤請儘快聯絡管管(?

Subtasks

For Testdata: 0 ~ 4, Score: 20
For Testdata: 5 ~ 9, Score: 20
For Testdata: 10 ~ 14, Score: 20
For Testdata: 15 ~ 19, Score: 20
For Testdata: 20 ~ 24, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 524288 65536
1 5000 524288 65536
2 5000 524288 65536
3 5000 524288 65536
4 5000 524288 65536
5 5000 524288 65536
6 5000 524288 65536
7 5000 524288 65536
8 5000 524288 65536
9 5000 524288 65536
10 5000 524288 65536
11 5000 524288 65536
12 5000 524288 65536
13 5000 524288 65536
14 5000 524288 65536
15 5000 524288 65536
16 5000 524288 65536
17 5000 524288 65536
18 5000 524288 65536
19 5000 524288 65536
20 5000 524288 65536
21 5000 524288 65536
22 5000 524288 65536
23 5000 524288 65536
24 5000 524288 65536