From: tho_mica_l <micathom@...>
Date: 2008-01-22T04:34:58+09:00
Subject: Re: Longest Repeated Substring (#153)

Hi,

With some delay, here is my solution. I started on Friday with my
take
on making suffix trees respect overlaps but then stopped. I have to
admit that it was Eric's solution that made take another look on
this.
The current version is about 3 times slower than Eric's submission.
It
passes all my test cases though. It also takes the idea from (IIRC)
Dave
Thomas's submission to calculate the original start position on the
basis of the string's length.

BTW it seems to me that ruby19 (cygwin, win xp) uses a __lot__ more
memory for this.

Regards,
Thomas.


#!/usr/bin/env ruby

class String
   def longest_substring_st4
        suffixes = Array.new(size) {|i| self[i..size]}
        suffixes.sort!
        common = ''
        comlen = 0
        suffixes.each_with_index do |curr, index|
            next if index == 0
            curridx = size - curr.size
            pindex  = index - 1
            pindex.downto(pindex - comlen) do |i|
                pred    = suffixes[i]
                psize   = pred.size
                predidx = size - psize
                maxlen  = [(predidx - curridx).abs, psize].min - 1
                next if maxlen < comlen
                prefix  = pred[0 .. comlen]
                break if prefix != curr[0..comlen]
                (comlen + 1 .. maxlen).each do |i|
                    p = pred[i]
                    c = curr[i]
                    if p == c
                        prefix << p
                    else
                        break
                    end
                end
                common = prefix
                comlen = common.size
                break if comlen <= maxlen
            end
        end
        return common
    end
end


if __FILE__ == $0
    if ARGV.empty?
        puts String.new(STDIN.read).longest_substring_st4
    else
        ARGV.each {|f| puts
String.new(File.read(f)).longest_substring_st4}
    end
end