bzoj#P3499. PA2009 Quasi-template

PA2009 Quasi-template

题目描述

定义一个串 ss 能匹配 SS 当且仅当 ss 能可超出头尾得覆盖 SS。如下图。

pic1

给定 SS,问不同的 ss 的个数。 SS 的长度 2105\leq 2 * 10^5

输入格式

The only line of the standard input contains a non-empty word that is not longer than 21052 * 10^5 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 vv. The second line should contain the shortest word being a quasi-template of word vv. 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.

数据规模与约定

保证输入的串长 2105\leq 2 * 10^5