--Apple-Mail-1--800807487
Content-Type: text/plain;
	charset-ASCII;
	formatðïwed
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  ,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  
>     self.build_nodes(s)
>     31.step(1,-5) do |kl|
>       lrs  elf.find_using_key_length(kl)
>       return lrs if lrs.length > 0
>     end
>     return ""
>   end
>
>  private
>
>   def self.find_using_key_length (kl)
>     long_len  
>     long_node  il
>     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  elf.length_at (v[i],v[j])
>           if len > long_len
>             long_len, long_node  en, v[i]
>           end
>         end
>       end
>     end
>     @@string.slice(long_node.index,long_len) rescue ""
>   end
>
>   def self.build_nodes(s)
>     prev  il
>     s.split(//).each_with_index do |c,i|
>       curr  ode.new(c,i)
>       prev.next  urr if prev
>       @@nodes << curr
>       prev  urr
>     end
>   end
>
>   def self.build_node_hash(key_length)
>     @@node_hash  ash.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  
>     b_index  .index
>     while b and a.char b.char and a.index ! _index
>       len + 
>       a,b  .next,b.next
>     end
>     len
>   end
>
> end
>
> if __FILE__ $0
>   puts LongestRepeatedSubstring.find(STDIN.read)
> end
>


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