Məsələlər
Təkrarlanan altardıcıllıqlar
Təkrarlanan altardıcıllıqlar
Siz dünyada səyyahət edən xazinə ovçularısınız. Axır ki, Sizin əlinizə xazinənin gizlədildiyinı göstərən qədim əl yazısı (manuskript) keçdi. İlk baxışda əl yazısının mətni mənasız simvollar sətri kimi görünür. Əslində isə xəzinənin yeri mətndə təkrarlanan ən böyük altardıcıllıq şəklində gizlədilmişdir.
Gəlin sətirdə təkrarlanan ən böyük altardıcıllığın nə olduğunu müəyyənləşdirək. Əvvəlcə verilmiş \textbf{S} sətrini iki \textbf{F} və \textbf{R} hissəyə ayıraq. \textbf{F} və \textbf{R} sətirlərinin ən böyük ortaq altardıcıllığını (\textbf{F} və \textbf{R}-in ən uzun altardıcıllığı olan \textbf{L} sətrini) tapaq. \textbf{S} sətrini iki hissəyə ayırmağın bir neçə üsulu olduğunu nəzərə alsaq, onda bir necə mümkün \textbf{L} altardıcıllığı müvcuddur. Təkrarlanan ən böyük altardıcıllıq onlardan ən böyüyüdür. Məsələn,\textbf{ }"\textbf{ABCABCABAB}" sətrinin təkrarlanan ən böyük altardıcıllığı "\textbf{ABAB}"-dır, çünki "\textbf{ABCABCABAB}" sətrini "\textbf{ABCABC}" и "\textbf{ABAB}" altsətirləinə ayırmaqla əldə olunur.
Sizdən təkrarlanan ən böyük altardıcıllığı təyin edərək gizlədilmiş xəzinəni tapmaq tələb olunur!
\InputFile
Giriş verilənləri bir neçə testi ehtiva edir. Hər bir test bir sətirdən ibarətdir və \textbf{300}-ə qədər böyük hərfləri ehtiva edə bilər. Zəmanət verilir ki, hər bir giriş sətri ən azı bir təkrarlanan alt ardıcıllığı ehtiva edir.
Sonuncu sətirdə "\textbf{#END}" verilir və emal edilmir.
\OutputFile
Hər bir test üçün ayrı sətirdə təkrarlanan ən böyük altardıcıllığı vermək tələb olunur. Əgər bu cür altardıcıllıqlardan bir neçəsi olarsa, onlardan hər hansı birini verməli.
Giriş verilənləri #1
ABCABCABAB ZZZZZZZZZZZZ #END
Çıxış verilənləri #1
ABAB ZZZZZZ