Algorithmathon Day 18: Longest Common Substring Revisited
Created: 9 September 2013 Modified:
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
tags: Algorithm - Algorithmathon - Longest Common Substring - RSpec - Ruby