Algorithmathon Day 18: Longest Common Substring Revisited
09 September 2013
We previously found the Longest Common Substring (LCS) using a trie on Day 13. Today our goal is to solve this problem a different way. This solution is O(n<sup>2</sup>) because it involves a loop within a loop. We will scan through the first string and for every character we will scan every character in the second string for a match. If a match is found we will then scan the next characters in both strings for a match. This means that the worst case scenario is when neither string has a matching sub-string. The solution should work something like this.
Read next character from string one.
Go to the beginning of string two.
Read next character from string two.
If the characters match read the next characters from both strings. Otherwise go to step 1.
If the characters match go to step 3. Otherwise record the substring and to to step 1.
As always we begin with our RSpec tests.
require 'spec_helper' describe AlgorithmString do describe "Class" do it "should have method 'longest_common_substring'" do AlgorithmString.method_defined?(:longest_common_substring).should be_true end end describe "Instance" do describe "Longest common substring method tests" do it "should return 'bcd' when ABCD.longest_common_substring(BCDE) is called" do a_string= AlgorithmString.new('ABCD') a_string.longest_common_substring('BCDE').should == 'BCD' end it "should return 'try' when TRY.longest_common_substring(RETRY) is called" do a_string= AlgorithmString.new('TRY') a_string.longest_common_substring('RETRY').should == 'TRY' end it "should return 'FGH' when ABCDFGHXYZ.longest_common_substring(TSVPFGHARS) is called" do a_string= AlgorithmString.new('ABCDFGHXYZ') a_string.longest_common_substring('TSVPFGHARS').should == 'FGH' end end end end
Now for our solution.
class AlgorithmString < String #Find the longest common substring with the #string_to_compare parameter. # * *Args* # - +string_to_compare+ -> A string which is compared to this string instance to find the longest common substring # * *Returns* # - A string that is the first longest common substring found. def longest_common_substring(string_to_compare) @longest_begin = -1 @longest_length = 0 unless self.length < 1 || string_to_compare.nil? || string_to_compare.length < 1 @current_outer = 0 while (@current_outer + @longest_length) < self.length @current_inner = 0 while @current_inner < string_to_compare.length if self[@current_outer] == string_to_compare[@current_inner] process_first_character_match(string_to_compare) break end @current_inner = @current_inner + 1 end @current_outer = @current_outer + 1 end end self.slice(@longest_begin,@longest_length) end private # Called from longest_common_substring when a first character match is found. # Advances to the next character in both strings to look for a match. # # - +string_to_compare+ -> A string which is compared to this string instance to find the longest common substring # # * *Returns* # - A string that is the matching characters found. def process_first_character_match(string_to_compare) current_begin=@current_outer current_length=1 @current_outer = @current_outer + 1 @current_inner = @current_inner + 1 while @current_outer < self.length && @current_inner < string_to_compare.length if self[@current_outer] == string_to_compare[@current_inner] current_length=current_length + 1 else break end @current_outer = @current_outer + 1 @current_inner = @current_inner + 1 end if current_length > @longest_length @longest_begin=current_begin @longest_length = current_length end end end