← 返回题目列表

Codeforces · 2045/H

H. 缺少分隔符

中文机器翻译题面 查看原题

你有一本字典,它是按字母顺序排序的不同单词的列表。每个单词均由大写英文字母组成。

您想要打印这本词典。但是,打印系统存在一个错误,列表中的所有单词都彼此相邻打印,单词之间没有任何分隔符。现在,您最终得到了一个字符串 $$$S$$$,它是字典中所有单词按列出顺序串联而成的。

您的任务是将 $$$S$$$ 拆分为一个或多个单词来重建字典。请注意,重建的字典必须由按字母顺序排序的不同单词组成。此外,您希望最大化词典中的单词数量。如果有多个可能的词典具有最大字数,您可以选择其中任何一个。

输入

由字符串 $$$S$$$ ($$$1 \leq |S| \leq 5000)$$$ 组成的单行。字符串 $$$S$$$ 仅由大写英文字母组成。

输出

首先,在单行中输出一个整数,表示重构词典中单词的最大数量。将此数字表示为 $$$n$$$。

然后,输出 $$$n$$$ 行,每行包含一个代表单词的字符串。单词必须不同,并且列表必须按字母顺序排序。按列出的顺序串联的单词必须等于 $$$S$$$。

如果存在多个可能的具有最大字数的词典,则输出其中任何一个。

示例

输入 #1

ABACUS

输出 #1

4
A
BA
C
US

输入 #2

AAAAAA

输出 #2

3
A
AA
AAA

输入 #3

EDCBA

输出 #3

1
EDCBA