From: James Koppel <jamesbkoppel@...>
Date: 2008-01-22T07:37:07+09:00
Subject: Re: [QUIZ] Longest Repeated Substring (#153)

My solution finds substrings of length n, groups the identical ones together in a hash of their starting indices, prunes out cases where two of the "repeated" substring overlap each other, and then looks in the same places for substrings of length n+1.

The aggressive pruning does, however, cause it to fail in the case where a substring that overlaps at one length does not overlap at a higher length. For example, take the string "aaaaaa". The substring "aa" exists at indicies [0,1,2,3,4]. My program will prune that down to [0,2,4]. It will then record the substring of length 3 that starts at each of [0,2,4], prune out the ones that start at 2 (overlaps with the one startign at 0) and 4 (goes out of bounds), leaving only an unrepeated substring, and would thus fall back and print "aa," even though the correct answer is "aaa," because the index of 3 had already been pruned.

On the other hand, the aggressive pruning does make my program somewhat fast. It takes about 45s on Also Sprach Zarathustra.

text = ARGF.read

substr_locs = {}

text.split(//).each_with_index do |c,idx|
  if substr_locs[c]
    substr_locs[c] << idx
  else
    substr_locs[c] = [idx]
  end
end

substr_locs.each_pair do |substr,locs|
  substr_locs.delete(substr) if locs.length == 1
end

len = 1
done = false
until done
  len += 1
  new_substr_locs = {}
  substr_locs.each_pair do |substr,locs|
    locs.each do |idx|
      s = text[idx,len]
      next if idx+len>text.length
      if new_substr_locs[s]
        new_substr_locs[s] << idx
      else
        new_substr_locs[s] = [idx]
      end
    end
  end
  ##Must reduce for the case where a substring overlaps itself
  new_substr_locs.each_key do |s|
    locs = new_substr_locs[s]
    idx = 1
    while idx < locs.length
      if locs[idx]-locs[idx-1] < len
        locs.delete_at(idx)
      else
        idx += 1
      end
    end
    new_substr_locs.delete(s) if locs.length == 1
  end
  unless new_substr_locs.keys.empty?
    substr_locs = new_substr_locs
  else
    done = true
  end
end
puts substr_locs.keys.first



      ____________________________________________________________________________________
Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  http://tools.search.yahoo.com/newsearch/category.php?category=shopping