준템플릿

단어 v 의 템플릿이란, v 안에서 s 가 나타나는 위치들이 모여 v 전체를 덮는 단어 s 를 말한다. 즉 v 의 모든 글자는 s 와 같은 연속된 글자 조각 중 적어도 하나에 포함된다.

단어 v 의 준템플릿이란, v 의 부분 문자열(연속된 글자 조각)이면서 v 의 어떤 확장 문자열(v 를 부분 문자열로 포함하는 문자열)의 템플릿이 되는 단어 s 를 말한다. 다시 말해, s 의 복사본들을 v 위에 겹쳐 놓아 v 의 모든 글자를 덮을 수 있으면 되며, 이때 가장 왼쪽과 가장 오른쪽 복사본은 겹치는 부분만 일치한다면 v 의 양 끝 밖으로 삐져나가도 된다.

아래 그림은 단어 aabaa 가 단어 aaaabaabaaaba 의 준템플릿인 이유를 보여 준다:

             aabaa
         aabaa
      aabaa
 aabaa
---------------------
    aaaabaabaaaba

주어진 단어 v 에 대해 서로 다른 준템플릿이 몇 개인지 구하고, 그중 가장 짧은 것을 찾아라.

입력의 유일한 줄에는 영어 소문자로만 이루어진, 길이가 200000 이하인 비어 있지 않은 단어 v 가 주어진다.

두 줄을 출력한다. 첫째 줄에는 v 의 서로 다른 준템플릿의 개수를 출력한다. 둘째 줄에는 v 의 가장 짧은 준템플릿을 출력한다. 가장 짧은 준템플릿이 여러 개이면 그중 사전순으로 가장 앞서는 것을 출력한다.

단어 aaaabaabaaaba 에는 10개의 준템플릿이 있다: aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, abaabaaa.