From: James Gray <james@...>
Date: 2008-01-21T00:58:48+09:00
Subject: Fwd: Please Forward: Ruby Quiz Submission

--Apple-Mail-1--800807487
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed
Content-Transfer-Encoding: 7bit

Begin forwarded message:

> From: "Clark Grubb" <clarkgrubb@gmail.com>
> Date: January 19, 2008 12:41:23 AM CST
> To: submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>
> class LongestRepeatedSubstring
>
>   class Node
>     attr_accessor :char, :next, :index
>     def initialize(c,i)
>       @char,@index = c,i
>     end
>   end
>
>   @@nodes = []
>
>   # Nodes are hashed by the substring starting at the
>   # node's position of a given length (the key_length).
>   # Using a large key_length makes the search faster, but if
>   # the largest repeated string is smaller than the key_length,
>   # we won't find any repeated strings.  Hence we try a smaller
>   # key_length when a search fails.
>   #
>   # There doesn't appear to be much of a speed increase for key_length
>   # above 30, at least for English text.
>
>   def self.find(s)
>     @@string = s
>     self.build_nodes(s)
>     31.step(1,-5) do |kl|
>       lrs = self.find_using_key_length(kl)
>       return lrs if lrs.length > 0
>     end
>     return ""
>   end
>
>  private
>
>   def self.find_using_key_length (kl)
>     long_len = 0
>     long_node = nil
>     self.build_node_hash(kl)
>     @@node_hash.each do |k,v|
>       0.upto(v.length-1) do |i|
>         (v.length-1).downto(i+1) do |j|
>           len = self.length_at (v[i],v[j])
>           if len > long_len
>             long_len, long_node = len, v[i]
>           end
>         end
>       end
>     end
>     @@string.slice(long_node.index,long_len) rescue ""
>   end
>
>   def self.build_nodes(s)
>     prev = nil
>     s.split(//).each_with_index do |c,i|
>       curr = Node.new(c,i)
>       prev.next = curr if prev
>       @@nodes << curr
>       prev = curr
>     end
>   end
>
>   def self.build_node_hash(key_length)
>     @@node_hash = Hash.new { |h,k| h[k] = [] }
>     @@nodes.each do |n|
>       @@node_hash[@@string.slice(n.index,key_length)] << n if n.next
>     end
>   end
>
>   # Length of the longest substring starting at both node a and node b
>   def self.length_at(a,b)
>     len = 0
>     b_index = b.index
>     while b and a.char == b.char and a.index != b_index
>       len += 1
>       a,b = a.next,b.next
>     end
>     len
>   end
>
> end
>
> if __FILE__ == $0
>   puts LongestRepeatedSubstring.find(STDIN.read)
> end
>


--Apple-Mail-1--800807487--