Memory limit: 192 MB
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
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
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:
Task author: Tomasz Idziaszek.