Skip to content

Instantly share code, notes, and snippets.

@Joseph-N
Created April 23, 2016 14:11
Show Gist options
  • Save Joseph-N/fbf061aa2347ed2c104f0b3fe1a5b9f2 to your computer and use it in GitHub Desktop.
Save Joseph-N/fbf061aa2347ed2c104f0b3fe1a5b9f2 to your computer and use it in GitHub Desktop.
Longest common substring ruby
def find_longest_common_substring(s1, s2)
if (s1 == "" || s2 == "")
return ""
end
m = Array.new(s1.length){ [0] * s2.length }
longest_length, longest_end_pos = 0,0
(0 .. s1.length - 1).each do |x|
(0 .. s2.length - 1).each do |y|
if s1[x] == s2[y]
m[x][y] = 1
if (x > 0 && y > 0)
m[x][y] += m[x-1][y-1]
end
if m[x][y] > longest_length
longest_length = m[x][y]
longest_end_pos = x
end
end
end
end
return s1[longest_end_pos - longest_length + 1 .. longest_end_pos]
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment