In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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:
the correct result is:
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.