From: SERGEY VOLKOV <gm.vlkv@...>
Date: 2008-01-24T21:17:26+09:00
Subject: Re: Longest Repeated Substring (#153)

It's linear search for repeated substring length,
I've tried binary search, too slow too

On Jan 24, 2008 12:39 AM, Ken Bloom <kbloom@gmail.com> wrote:
>
> On Wed, 23 Jan 2008 13:21:31 -0500, SERGEY VOLKOV wrote:
>
> > Why not?
> > The simplest solution could be:
> >
> > def longest_repeated_substring str
> >     (str.size/2).downto(1) { |i|
> >         /(.{#{i}}).*\1/m =~ str and return $1
> >     }
> >     nil
> > end
> >
> > but it's too slow;
> >
> > On Jan 23, 2008 12:35 PM, Raffa <raffaboss@gmail.com> wrote:
> >> cannot use regex, i suppose:
> >>
> >> (.{aNumber}).*\1
> >>
> >>
> >>
> >> where aNumber = 2..x (x=text.length/2), until regex 'response' is 'nil'
>
> Well, one would think that the absolute simplest solution is /(.*+).*\1/,
> but that's what I was testing when I invented the "your banana my banana"
> test case. (Which it failed, returning only "y" as the repeated
> substring).
>
> Yours is a nice extension of this basic idea.
>
>
> --Ken
>
> --
> Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
> Department of Computer Science. Illinois Institute of Technology.
> http://www.iit.edu/~kbloom1/
>
>