bzoj#P3499. PA2009 Quasi-template
PA2009 Quasi-template
题目描述
定义一个串 能匹配 当且仅当 能可超出头尾得覆盖 。如下图。
给定 ,问不同的 的个数。 的长度 。
输入格式
The only line of the standard input contains a non-empty word that is not longer than 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 . The second line should contain the shortest word being a quasi-template of word . 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.
数据规模与约定
保证输入的串长