PA2009 Quasi-template

题目描述

定义一个串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.

 

---

题目来源

没有写明来源