You are to write the shortest complete program that takes a string as input from STDIN and decomposes it as far as possible, and prints the composition to STDOUT.
To decompose a string, your program finds a substring (of length greater than 1) within the original string, the repetitions of which take up a much of the string as possible. It then creates several new strings, one of which is that substring and the others are the original, split apart at where the substring occurred. You then repeat this process of finding a substring whose repetitions take up as much of those strings as possible.
The end of input is reached when there is a newline (
Output should consist of each substring in the order that it is found, followed by two newlines, followed by everything left at the end of decomposition sorted from longest to shortest, all separated by line breaks.
Happy birthday to you! Happy birthday to you! Happy birthday to somebody! Happy birthday to you!
The longest repeated substring is
Happy birthday to you!; however, the substring
Happy birthday to (with a space after the "to") takes up more space because there is one more repetition of it. The
Happy birthday to is outputted. You then end up with several new strings.
Happy birthday to (with space at the end) you! (with space) you! (with space) somebody! (with space) you!
Here, the substring
you!is repeated the most. Even though it is not repeated within any individual string, it is repeated multiple times throughout all of the strings. The
you! is outputted. Now you have
Happy birthday to (with space) you! (lone space character) (lone space) somebody! (with space)
Here, the substring
y(with space) is repeated the most. The
y is outputted. Now you have
Happ birthda to (with space) y (with space) you! (lone space character) (lone space) somebody! (with space)
As far as I can tell, there are no more substrings of length > 1 (the spaces are only one character). You then output each substring that you found, followed by what is above.
Happy birthday to you! y somebody! birthda Happ you! to y
There should be two lines of just a space at the end, but those are not being displayed. There should also be a space after that single y.