TopCoder

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

User's AC Ratio

60.0% (18/30)

Submission's AC Ratio

15.4% (59/384)

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

No. Testdata Range Score
1 0~4 20
2 5~9 20
3 10~14 20
4 15~19 20
5 20~24 20

Testdata and Limits

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