From: Dave Thomas <dave@...>
Date: 2008-01-21T02:04:03+09:00
Subject: Re: [QUIZ] Longest Repeated Substring (#153)

My hack at the substring problem (nice one, James) is based on suffix  
trees.

Suffix trees and suffix arrays and a great tool for substring  
operations. The idea is to create a list of all the possible suffixes  
in the original string. For "banana" this would be

banana
anana
nana
ana
na
a

Because the list contains an entry starting at every position in the  
string, we know that all possible substrings of the original string  
must occur at the start of one of these list elements. The substring  
"nan", for example, occurs at the start of the 3rd entry.

Now sort them

a
ana
anana
banana
na
nana

Now we know that all substrings that start with the same sequence of  
characters must occur at the start of items in the list that are  
adjacent. Searching through to list to find these is a linear operation.

A suffix array is basically this data structure. For efficiency,  
though, it doesn't store the actual strings. Instead it stores the  
offset of the start of the string (for our example, this would be [6,  
4, 2, 1, 5, 3]). You'll find a whole bunch of stuff on using suffix  
arrays for searching and string matching, particularly in the area of  
DNA sequencing.

It turns out that in Ruby, you don't always have to go to the trouble  
of constructing the suffix array. When you take a substring in Ruby,  
it doesn't copy the string data. Instead, it just constructs a new  
string object (just a few words of memory) that references into the  
original string. Only when either string is modified does the string  
content get copied. This means the code for constructing the suffix  
list is both simple and relatively efficient:

   def initialize(text)
     @suffix_list = []
     len = text.length
     len.times { |i| @suffix_list << text[i, len] }  # the ,len] is a  
hack...
     @suffix_list.sort!
   end

The only ugly part is the use of [i, len] to create the substring.  
Technically it should be 1..len, but that constructs a new,  
unnecessary range object. Using 'len' as the final index does the same  
thing, because the substring stops at the end of the input string, but  
it can be misleading to read.

The code to scan the suffix list looks at each adjacent pair, and sees  
if it can find a longer matching substring at the start of each that  
it has previously found. Because James disallowed overlapping  
substrings, you have to be careful to look at no more that 1/2 of the  
longest string. The basic loop looks like this:


     s1 = @suffix_list[0]

     1.upto(@suffix_list.size - 1) do |i|

       s2 = @suffix_list[i]
       max_possible = s2.length / 2   # stop them overlapping

       while  # quick sanity check - saves doing the more expensive  
substring if it fails
              s1[max_length_so_far] == s2[max_length_so_far] &&
              # stop strings from overlapping
              max_length_so_far < max_possible &&
              # brute force comparison
              s1[0,max_plus_one] == s2[0,max_plus_one]

         max_length_so_far = max_plus_one
         max_plus_one += 1
         found_at = i
       end
       s1 = s2
     end

The while loop has three conditions. The last one is the money earner:  
it looks for a match at the start of the two strings which is one  
longer that the longest match found so far. If it finds it, it records  
this as the new longest match, and then tries for a even longer one  
with the current pair.

The second condition on the while loop stops us considering more than  
1/2 the second string. Because our strings are sorted, if thereis  
overlap, the second string will always be the one that contains the  
overlapping segment of the first.

The first condition is just an optimization: it stops us doing the  
more expensive substring comparison if the last characters of the two  
substrings we're comparing don't match.

So, put it all together, and we have

# - - - - - - - - - - - - -

class CommonSeq

   def initialize(text)
     @suffix_list = []
     len = text.length
     len.times { |i| @suffix_list << text[i, len] }  # the ,len] is a  
hack...
     @suffix_list.sort!
   end

   def find_substrings
     max_length_so_far = 0
     max_plus_one      = 1    # save a little math in the loop
     found_at          = nil

     # Look at all adjacent pairs of suffices.
     s1 = @suffix_list[0]

     1.upto(@suffix_list.size - 1) do |i|

       s2 = @suffix_list[i]
       max_possible = s2.length / 2   # stop them overlapping

       while  # quick sanity check - saves doing the more expensive  
substring if it fails
              s1[max_length_so_far] == s2[max_length_so_far] &&
              # stop strings from overlapping
              max_length_so_far < max_possible &&
              # brute force comparison
              s1[0,max_plus_one] == s2[0,max_plus_one]

         max_length_so_far = max_plus_one
         max_plus_one += 1
         found_at = i
       end
       s1 = s2
     end

     if found_at
       suffix = @suffix_list[found_at]
       [max_length_so_far, suffix[0, max_length_so_far]]
     else
       nil
     end
   end
end

if __FILE__ == $0
   seq = CommonSeq.new(STDIN.read.chomp)
   puts seq.find_substrings
end

# - - - - - - - - - - - - -


Run times are shown for the Illiad and War and Peace:

   dave[tmp/seq] time ruby seq.rb <homer.txt
   168
    who are
   perishing and coming to a bad end. We will, however, since you so
   bid us, refrain from actual fighting, but we will make serviceable
   suggestions to the Argives
   ruby seq.rb < homer.txt  2.82s user 0.05s system 99% cpu 2.872 total


   dave[tmp/seq] time ruby seq.rb <war.txt
   63


   The Project Gutenberg Literary Archive Foundation has been
   ruby seq.rb < war.txt  12.49s user 0.17s system 99% cpu 12.737 total


Here's the somewhat basic set of tests I used


# - - - - - - - - - - - - -
require 'seq'
require 'test/unit'

class CommonSeq
   attr_reader :suffix_list
end

class TestSeq < Test::Unit::TestCase

   def test_basic_suffix_creation
     cs = CommonSeq.new("banana")
     assert_equal(%w{a ana anana banana na nana}, cs.suffix_list)
   end

   def test_empty
     cs = CommonSeq.new("")
     assert_nil cs.find_substrings
   end

   def test_length_one
     cs = CommonSeq.new("a")
     assert_nil cs.find_substrings
   end

   def test_length_two_no_match
     cs = CommonSeq.new("ab")
     assert_nil cs.find_substrings
   end

   def test_length_two_with_match
     cs = CommonSeq.new("aa")
     assert_equal [ 1, "a"],  cs.find_substrings
   end

   def test_length_three_no_match
     cs = CommonSeq.new("abc")
     assert_nil cs.find_substrings
   end

   def test_length_three_adjacent_match
     cs = CommonSeq.new("aab")
     assert_equal [ 1, "a"],  cs.find_substrings
   end

   def test_length_three_separated_match
     cs = CommonSeq.new("aba")
     assert_equal [ 1, "a"],  cs.find_substrings
   end

   def test_does_not_find_overlapping_match_length_one
     cs = CommonSeq.new("aaa")
     assert_equal [ 1, "a"],  cs.find_substrings
   end

   def test_does_not_find_overlapping_match_length_three
     cs = CommonSeq.new("aaaa")
     assert_equal [ 2, "aa"],  cs.find_substrings
   end

   def test_does_not_find_overlapping_match_length_two
     cs = CommonSeq.new("ababa")
     assert_equal [ 2, "ab"],  cs.find_substrings
   end

   def test_banana
     cs = CommonSeq.new("banana")
     assert_equal [ 2, "an"],  cs.find_substrings
   end
end
# - - - - - - - - - - - - -


I wouldn't be surprised if the idea of searching only 1/2 of the  
second string to prevent overlaps is wrong.. :)


Dave