Decompose a String

Question

Challenge

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 (/n).

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.

Example

input

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.

Total Output

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.

Answer 1

Ruby, 232 characters

i=[gets.chop]
while l=((0..-2+n=(v=i*'').size).map{|s|(s+1..n).map{|m|c=v[s..m]
u=[i.map{|t|t.split(c)},c].flatten
v.size>(w=(u*'').size)&&[w,c,u]}}.flatten(1)-[false]).sort[0]
puts l[1]
i=l[2]
end
puts
i.sort_by!{|k|-k.size}
puts i

This code reflects my first idea towards the problem. Actually it took much more characters than I thought initially. Nevertheless I still hope to find a shorter solution using a different approach.

Answer 2

If you allow for the weak definition of a substring, then here's a trivial solution.

R, 9 characters (10 with \n)

d=scan()
d

But I suspect you mean strict substring, in which case parroting back the input string will not suffice :-)

R, not yet condensed

d <- "Happy birthday to you! Happy birthday to you! Happy birthday to somebody! Happy birthday to you!"
#d=scan()
# Shorten things
l=list
# Break up into consituent parts
e=strsplit(d,"")[[1]]
g=l()
for(i in 1:nchar(d)) g[[i]]=embed(e,i) 
g=lapply( g, function(x) apply(x,1,paste,collapse="") )
# Find max coverage (function takes each element of the g list and returns max X its length) (if type=2 then returns the string instead)
m=function(x,t=1) {
  r=rle(sort(x))
  w=which.max(r$l)
  if(all(r$l[w]<2)) return(0)
  v=r$v[w]
  switch(t,r$l[w]*nchar(v),v)
}
m(g[[which.max(sapply(g,m))]],2)

Which returns " ot yadhtrib yppaH !uoy ot yadhtrib yppaH".

Easy enough to reverse and to iterate this over the remaining string, but I'm going to hold off pending clarification of whether overlapping substrings are allowed. I suspect not from the example, but this one has more coverage (82 characters) if so.