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(n2) 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.algorithm_string_spec.rb
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.algorithm_string_spec.rb
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