PA2009 Quasi-template

时间限制:10s      空间限制:256MB

题目描述

定义一个串s能匹配S当且仅当s能可超出头尾得覆盖S。  如下图。
  
给定S,问不同的s的个数。
S的长度 <  = 200000。


输入格式

The only line of the standard input contains a non-empty word that is not longer than 200000 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.

 


题目来源

没有写明来源