Generator for a test case of this problem. A certain Icelandic singer absolutely hates repeating himself. It seems tedious and not very interesting to him.
This means each word he says is not equal to a string concatenated $$$2$$$ or more times. Formally, he can say a word $$$w$$$, if $$$w$$$ cannot be written as $$$s + s + \cdots + s$$$ ($$$k$$$ times, with $$$k \gt 1$$$). So he cannot say "hahaha" (can be written as "ha" + "ha" + "ha"), but he can say "endurtakamig". (The phrase "Endurtaka mig" is Icelandic for "Repeat myself".) You are analyzing a sentence spoken by the singer. You only forgot to add spaces between the words, so you are looking for an optimal way to do so. What is the minimum number of words to split the string into, such that each word could have been spoken by this singer?
The input consists of:
- One line with a string $$$s$$$ ($$$1\leq |s|\leq {3\cdot10^5}$$$), the sentence spoken.
Output the minimum number of words $$$k$$$ in the sentence, followed by $$$k$$$ strings which form a possible subdivision of the sentence into words.
If there are multiple valid solutions, you may output any one of them.
hahaha
2 hah aha
endurtakamig
1 endurtakamig
