[PA2009] Quasi-template

题目描述

定义一个串 $s$ 能匹配 $S$ 当且仅当 $s$ 能可超出头尾地覆盖 $S$ 且长度不超过 $S$，且 $s$ 必须是 $S$ 的子串。

如下图。

给定 $S$ ，求不同的 $s$ 的个数以及长度最短的 $s$，如有多解，输出字典序最小的。

输入格式

一行一个字符串 $S$。

输出格式

第一行一个整数表示方案数。

第二行一个字符串，表示长度最短的 $s$，如有多解，输出字典序最小的。

样例 #1

样例输入 #1

aaaabaabaaaba

样例输出 #1

10
aabaa

提示

符合条件的串： aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, abaabaaa.

$S$ 的长度 $\leq 2\times 10^5$