From: Urs Meyer <ursmr@...>
Date: 2008-01-22T21:58:28+09:00
Subject: Re: [QUIZ] Longest Repeated Substring (#153)

Hi there,

thought first of two loops, one that moves the start position
of the candidate substring, and another that makes it longer.  
It turned out that one loop that combines both is sufficient.

Without considering searching (text.index) the loop is O(n).
However, the index method is O(n). Thus, worst case (for my
program) is O(n^2).

Can one do it in O(n*log(n))? 

--

#!/usr/bin/ruby
#
# ruby quiz 153 - longest repeated substring
#
# print the first one found if several such substrings exist
#
# Urs Meyer, 2008-01-22

--

# read text from STDIN, convert to lower case, as you like
text = STDIN.read.tr("\nA-Z"," a-z")

# start position, determines the remaining search space
start = 0
longest_substring = ""

# search while remaining search space is at least twice the
# the size of the currently longest substring

while (2 * longest_substring.size) < (text.length - start)

    # generate substring to search for with size is one bigger
    # than longest found so far
    substring = text[start...(start+longest_substring.size+1)]

    # search for it
    i = text.index(substring, start+substring.size)

    if i.nil?
        # nothing found, advance start position
        start += 1
    else
        # found a longer one, record it
        longest_substring = substring
    end
end

puts longest_substring

--

$ echo banana | ruby lrs.rb
an
$ echo aa | ruby lrs.rb
a
$ echo aaa | ruby lrs.rb
a
$ echo aaaa | ruby lrs.rb
aa
$

some timings...

using random characters:
$ ruby -e "puts Array.new(100000){('a'[0]+rand(26)).chr}.join" | ( time ruby lrs.rb > /dev/null )
21.015u 0.046s 0:21.39 98.4%    0+0k 0+0io 1636pf+0w

with just a bunch of 'a's the job is easier:
$ ruby -e "puts 'a'*100000" | ( time ruby lrs.rb > /dev/null )
3.390u 0.015s 0:03.50 97.1%     0+0k 0+0io 3705pf+0w

lets see whether the result is correct:
$ ruby -e "puts 'a'*100000" | ruby lrs.rb | wc -c
50001

oops, but
$ echo "a" | wc -c
2

o.k. we are fine

if you are curious, I ran it a few times on 100000 random chars:
lnxmfqu
nvpban
ibhwilj
eggfur
mbljqx
gzvxhw
...

~~
Regards
Urs


-- 
GMX FreeMail: 1 GB Postfach, 5 E-Mail-Adressen, 10 Free SMS.
Alle Infos und kostenlose Anmeldung: http://www.gmx.net/de/go/freemail