URI Online Judge | 1234

A Ordem da Fênix

Por Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

Dentre as mais importantes rodovias que cruzam o estado de Santa Catarina estão a BR282, que o cruza de leste a oeste, e a BR153, que cruza praticamente o Brasil inteiro de norte a sul. O encontro entre essas duas rodovias é conhecido popularmente como Trevo de Irani, porque ocorre na cidade de Irani, ou Trevo da Fênix, porque sua forma, vista de cima, lembra a criatura mítica fênix, conforme mostra a Figura. A região do estado em que fica o Trevo da Fênix é chamada de Vale do Contestado, porque foi palco de uma das mais importantes guerras civis da história do Brasil: a Guerra do Contestado (1912–1916), entre rebeldes da população cabocla, sob a liderança notória do monge José Maria dentre outras, e tropas federais do Exército Brasileiro, sob a liderança notória do Cel. João Gualberto dentre outras.

Conta-se que, certa vez, um grupo de rebeldes fugia desesperado das tropas do Exército e veio parar no Trevo da Fênix. Frustrado com a batalha que haviam perdido no dia, um deles chutou o pó da terra. O vento levantou o pó, o qual, na verdade, não era pó, mas cinzas, e por um momento os caboclos viram uma fênix, que lhes deu uma Ordem: “Morse!”. Tendo regressado ao acampamento no dia seguinte e contado a história ao monge José Maria, os caboclos passaram a estudar o Código Morse, a interceptar mensagens das tropas do Cel. João Gualberto e a tentar identificar padrões repetidos nessas mensagens.

Entrada

A entrada é composta por uma cadeia S de no mínimo 1 e no máximo 105 caracteres, finalizada por uma quebra de linha, a qual representa uma mensagem interceptada. Além da quebra de linha, apenas os caracteres ‘.’ (ponto) e ‘-’ (traço) compõem a entrada.

Saída

Imprima uma linha composta unicamente da maior subcadeia de S com no mínimo 3 caracteres que se repete em S no mínimo uma vez. Se há mais de uma subcadeia que se repete com comprimento máximo, imprima a primeira delas em ordem lexicográfica, lembrando que o caractere ‘-’ aparece antes na tabela ASCII que o caractere ‘.’. Se não há subcadeias de S com comprimento no mínimo 3 que se repetem, a linha de saída deve ser composta unicamente do caractere ‘*’.

Exemplos de Entrada Exemplos de Saída

.---.-..--

.--

-.-.-.-.-.-.-

-.-.-.-.-.-

-.--...

*