W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
A template of a word is such a word that all occurrences of within cover the whole word (i.e. each letter of the word appears within some fragment of consecutive letters of equal to ). By quasi-template of a word we mean such a word that is a substring (i.e. a fragment of consecutive letters) of and is a template of some superstring of . The figure below shows why the word aabaa is a quasi-template of the word aaaabaabaaaba:
For a given word we would like to compute the number of its quasi-templates and the shortest one of them.
The only line of the standard input contains a non-empty word that is not longer than letters. It consists of small letters of English alphabet.
The first line of the standard output should contain the number of quasi-templates of word . The second line should contain the shortest word being a quasi-template of word . If there is more than one such shortest word, output the lexicographically smallest from the shortest quasi-templates.
For the input data:
aaaabaabaaaba
the correct result is:
10 aabaa
The word from the sample input has 10 quasi-templates: aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, and abaabaaa.
Task author: Tomasz Idziaszek.