Algorithmen und Datenstrukturen

Suche überall!

Angenommen, wir haben einen sehr langen Text t. Das Unternehmen möchte die längste Teilzeichenkette s finden, die alle folgenden Bedingungen erfüllt:
  • s ist ein Präfix von t
  • s ist ein Suffix von t
  • s ist irgendwo in t enthalten (d. h. s ist eine Teilzeichenkette von t)
Könnt ihr ihnen dabei helfen?

Eingabe

Die einzige Zeile der Eingabe enthält den Text t (1 ≤ |t| ≤ ).

Ausgabe

Das Programm soll die längste mögliche Zeichenkette s ausgeben, die alle Bedingungen erfüllt, oder Impossible ausgeben, falls keine entsprechende Zeichenkette gefunden werden kann.

Beispiele

Eingabe
Ausgabe
fixfixfix
fix
hello
Impossible
abcabdab
ab
 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue