시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 19 | 0 | 0 | 0.000% |
A template of a word v is such a word s that all occurrences of s within v cover the whole word v (i.e. each letter of the word v appears within some fragment of consecutive letters of v equal to s). By quasi-template of a word v we mean such a word s that s is a substring (i.e. a fragment of consecutive letters) of v and s is a template of some superstring of v. The figure below shows why the word aabaa
is a quasi-template of the word aaaabaabaaaba
:
aabaa aabaa aabaa aabaa --------------------- aaaabaabaaaba
For a given word v 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 v that is not longer than 200 000 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 v. The second line should contain the shortest word being a quasi-template of word v. If there is more than one such shortest word, output the lexicographically smallest from the shortest quasi-templates.
aaaabaabaaaba
10 aabaa
The word from the sample input has 10 quasi-templates: aaaabaabaaab
, aaaabaabaaaba
, aaabaaba
, aaabaabaa
, aaabaabaaa
, aaabaabaaaba
, aabaa
, aabaabaa
, aabaabaaa
, and abaabaaa
.
Contest > Algorithmic Engagements > PA 2009 5-4번