Algoritmos e Estruturas de Dados

Procure em Todo o Lado!

Dado um texto muito extenso t, a empresa quer encontrar a substring mais longa s que cumpra vários requisitos:
  • s é um prefixo de t
  • s é um sufixo de t
  • s é uma substring de t
Consegue ajudá-los com isso?

Entrada

A única linha da entrada contém o texto t (1 ≤ |t| ≤ ).

Saída

O programa deve imprimir a substring mais longa s que atenda a todos os requisitos, ou Impossible caso não seja possível encontrar tal substring.

Exemplos

Entrada
Saída
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