From: Guillaume Carbonneau <guillaume.carbonneau@...>
Date: 2008-01-21T03:10:34+09:00
Subject: Re: [QUIZ] Longest Repeated Substring (#153)


Here is my solution using Suffix arrays

class SuffixArray
  attr_accessor :suffix_array
  def initialize(the_string)
    @the_string = the_string
    @suffix_array = Array.new
    #build the suffixes 
    last_index = the_string.length-1
    (0..last_index).each do |i|
      the_suffix = the_string[i..last_index]
      the_position = i
      # << is the append (or push) operator for arrays in Ruby
      @suffix_array << { :suffix=>the_suffix, :position=>the_position }
    end
      
    #sort the suffix array
    @suffix_array.sort! { |a,b| a[:suffix] <=> b[:suffix] }
  end
    
end

text = STDIN.read

highest_count = 0
longest_string = ""
sa = SuffixArray.new(text)
sa.suffix_array.each_with_index do |s,i|
  j = 1
  if sa.suffix_array[i+1]
    while sa.suffix_array[i][:suffix][0,j] ==
sa.suffix_array[i+1][:suffix][0,j]
      if j > highest_count
        highest_count = j
        longest_string = sa.suffix_array[i][:suffix][0,j]
      end
      j += 1
    end
  end

end
p longest_string

---------------------


I get the following times

ILLIAD :
$ time cat homer-illiad.txt | ruby suffix.rb 
" who are\nperishing and coming to a bad end. We will, however, since you
so\nbid us, refrain from actual fighting, but we will make
serviceable\nsuggestions to the Argives"

real	1m15.566s
user	1m14.810s
sys	0m0.410s

WAR AND PEACE
$ time cat wrnpc12.txt | ruby suffix.rb 
"\r\n\r\nThe Project Gutenberg Literary Archive Foundation has been "

real	4m55.145s
user	4m49.979s
sys	0m1.951s


-- 
View this message in context: http://www.nabble.com/-QUIZ--Longest-Repeated-Substring-%28-153%29-tp14953800p14984651.html
Sent from the ruby-talk mailing list archive at Nabble.com.