P15675 [ICPC 2024 Jakarta R] Missing Separators

你有一本**词典**，它是一个由互不相同的单词组成的列表，这些单词按**字典序**（字母顺序）排序。每个单词仅由大写英文字母组成。 你想打印这本词典。然而，打印系统存在一个错误，导致列表中的所有单词在打印时彼此紧挨着，单词之间没有任何分隔符。最终，你得到了一个字符串 $S$，它是词典中所有单词按列表顺序拼接而成的结果。 你的任务是通过将 $S$ 分割成一个或多个单词来**重建**这本词典。注意，重建后的词典必须由互不相同的单词组成，并且按字典序排序。此外，你希望**最大化**词典中的单词数量。如果有多个单词数量最多的可能词典，你可以选择其中任意一个。

一行，包含一个字符串 $S$（$1 \leq |S| \leq 5000$）。字符串 $S$ 仅由大写英文字母组成。

首先，在一行中输出一个整数，表示重建词典中单词的最大数量。记这个数为 $n$。 然后，输出 $n$ 行，每行包含一个字符串，表示一个单词。这些单词必须互不相同，并且列表必须按字典序排序。这些单词按列表顺序拼接后必须等于 $S$。 如果有多个单词数量最多的可能词典，输出其中任意一个。

翻译由 DeepSeek V3.2 完成