------art_9576_32473740.1200839418641
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Here is my solution. It is easy to follow but breaks down on larger inputs:


# Find first non-overlapping repeated substring contained in the input
string.
# Search space is smaller for longer substrings, so search for longest ones
first.
# Returns - Longest repeated substring, or nil if none
def longest_repeated_substring(input)
  len  nput.size / 2 # Max size is half total length, since strings cannot
overlap

  while len > 0
    # Find all substrings of given length
    sub_strings  }
    for i in 0...input.size-len
      sub_str  nput[i..i+len]

      if not sub_strings.has_key?(sub_str)
        sub_strings[sub_str]  +len # Add to list, track end pos for
overlaps
      elsif sub_strings[sub_str] < i
        return sub_str  # First non-overlapping match ties for longest
      end
    end

    len - 
  end

  nil
end

puts longest_repeated_substring(ARGV[0])


Thanks,

Justin

------art_9576_32473740.1200839418641--