24. E.太陽精靈的項練

0 Judge

Code: 0


E.太陽精靈的項練

題目敘述

Flareon

在大家的一陣嘻笑聲中,一個不小心,水精靈的水柱噴濺到十分愛乾淨的太陽精靈身上,把太陽精靈一條很寶貝的項鍊弄髒了。伊布們嚇死了!趕緊衝衝上前賠罪,並幫他把項鍊給擦拭乾淨。

在他們忙著打理太陽精靈的同時,皮卡丘發現一件有趣的事,這條項鍊似乎是由同一種圖騰重複拼接起來而形成的,我們把每一種圖示用一個符號代替,那這條項鍊可以表示成$ABBABBABBABB$,那可以發現項鍊可以由圖騰$ABBABB$或$ABB$組成,因為太陽精靈是完美主義者,不能有一個圖騰因項鍊長度不夠而被截斷,這樣太不完美了!此時太陽精靈走了過來,告訴皮卡丘說可以組成項鍊的圖騰很多種,但其實只有最短的那個才是真正的圖騰,因為那才最精簡的美阿!

之後太陽精靈帶來了好幾條項鍊,說如果皮卡丘如果可以分辨項鍊上的圖騰是什麼的話,那它可以把這些條項鍊送給皮卡丘作為初次見面的禮物。你能幫皮卡丘分辨圖騰嗎?或許他會送其中你一條漂亮的項鍊的!

輸入說明

有多筆輸入,每筆輸入佔1行。
每行有一串字代表項鍊的樣子,項鍊的每個圖示都會用一個大寫字母來表示。

保證在所有狀況下項鍊的長度$L$滿足$0< L\leq 5*10^7$

輸出說明

對於每筆輸入都輸出一行,為該項鍊的圖騰樣式。

範例輸入1

ABBABBABBABB

範例輸出1

ABB

範例輸入1

ABCBABCBA

範例輸出1

ABCBABCBA

配分方法

  • 0% 範例資料
  • 30% $L\leq 10$
  • 50% $L\leq 1000$
  • 70% $L\leq 10^6$
  • 100% $L\leq 5*10^7$

By LFsWang

Judge Setting

run-time limit: 3000 ms
memory limit: 76972032 byte
測資數量: 0