From: "Eric I." <rubytraining@...>
Date: 2008-01-21T04:24:56+09:00
Subject: Re: Longest Repeated Substring (#153)

On Jan 20, 12:04 pm, Dave Thomas <d...@pragprog.com> wrote:
> I wouldn't be surprised if the idea of searching only 1/2 of the  
> second string to prevent overlaps is wrong.. :)

I think you're right in that it's wrong.  ;)

If you submit the string "ababab" to your program, it comes back with
"aba" as the longest non-overlapping substring, but the answer should
be "ab".  When you compare the consecutive sorted suffixes "abab" and
"ababab", you allow strings up to 3 ("ababab".size / 2) to be used,
but in fact, they overlap in all but 2 characters.

I'll post my solution in a reply, which is very similar to your except
in the overlap prevention code, which, I have to admit, is pretty
ugly.  And I'm not even convinced that I got it right!

Eric