LCSubstring.rb

require 'rspec'
# function LCSubstr(S[1..m], T[1..n])
#     L := array(1..m, 1..n)
#     z := 0
#     ret := {}
#     for i := 1..m
#         for j := 1..n
#             if S[i] == T[j]
#                 if i == 1 or j == 1
#                     L[i,j] := 1
#                 else
#                     L[i,j] := L[i-1,j-1] + 1
#                 if L[i,j] > z
#                     z := L[i,j]
#                     ret := {S[i-z+1..i]}
#                 elif L[i,j] == z
#                     ret := ret ∪ {S[i-z+1..i]}
#             else
#                 L[i,j] := 0
#     return ret
#

class Coolstuff
  def self.longest_common_sub_string(string1, string2)
    character_map1 = string1.each_char
    character_map2 = string2.each_char
    longest = {}
    z = 0
    ret = {}


    character_map1.each_with_index do |i, i_index|
      character_map2.each_with_index do |j, j_index|
#       if S[i] == T[j]
        if i == j

#         if i == 1 or j == 1
          if i_index == 1 || j_index == 1

#           L[i,j] := 1
            longest[i_index, j_index] = 1

#         if L[i,j] > z
          elsif longest[i_index,j_index] > z
#           z := L[i,j]
#           ret := {S[i-z+1..i]}

#         elif L[i,j] == z
          elsif longest[i_index, j_index] == z
#           ret := ret ∪ {S[i-z+1..i]}
          end

        else
#         L[i,j] := 0
          longet[i_index, j_index] = 0
        end
      end
    end

  end
end

describe "longest_common_sub_string" do
  it "finds longest common sub string" do
    string1 = "BLAH ZORZ BLAHBLAHBLAH"
    string2 = "ASDOFMEITHING  BLAHBLAHBLAH"
    expect(Coolstuff.longest_common_sub_string(string1, string2)).to eq("BLAHBLAHBLAH")
  end
end