URI Online Judge | 1234

The Order of the Phoenix

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

Among the most important highways that cross the Brazilian state of Santa Catarina are the BR282, which crosses the state from east to west, and the BR153, which crosses almost the whole country from north to south. The intersection of these two highways is popularly known as Trevo de Irani (literally ‘Irani's Clover’, for, in Brazilian Portuguese, the same word used for clovers, ‘trevo’, is used for simple highway intersections), because it is located in the city of Irani, or Trevo da Fênix (literally ‘Phoenix's Clover’), because its shape, when viewed from above, reminds the mythical creature phoenix, as shows the Figure. The region of the state in which is located the Trevo da Fênix is called Vale do Contestado (literally ‘Valley of the Contested’), because it was in this region that happened one of the most important civil wars of Brazilian history: the Guerra do Contestado (literally ‘War of the Contested’), between rebels of the people known as caboclos, under the notorious leadership of the monk José Maria among others, and federal troops of Brazilian Army, under the notorious leadership of the Col. João Gualberto among others.

It is said that, once, a group of rebels was running desperate from the Army troops and happened to come to the Trevo da Fênix. Frustrated with the battle they had lost that day, one of them kicked the dust of the ground. The wind lifted the dust, which in fact was not dust, but ashes, and for a moment the caboclos saw a phoenix, that gave them an Order: “Morse!”. Back to the camp on the next day and having told the story to the monk José Maria, the caboclos started to study the Morse Code, to intercept messages from the Col. João Gualberto's troops and to try to identify repeated patterns in those messages.


The input consists of a single string S of at least 1 and at most 105 characters, ended by an end-of-line, which represents an intercepted message. Aside from the end-of-line, the string consists only of the characters ‘.’ (dot) and ‘-’ (dash).


Print a line consisting only of the longest substring of S with at least 3 characters that is repeated in S at least once. If there is more than a substring which is repeated with maximum length, print the first of them in lexicographical order, remembering that the character ‘-’ appears in the ASCII table before the character ‘.’. If there are no substrings of S with length at least 3 that are repeated, the output line shall consist only of the character ‘*’.

Input Samples Output Samples