Module: Rya::CoreExtensions::String

Defined in:
lib/rya/core_extensions.rb

Instance Method Summary collapse

Instance Method Details

#longest_common_substring(other) ⇒ Object

Note:

This is the algorithm from www.geeksforgeeks.org/longest-common-substring/

Use dynamic programming to find the length of the longest common substring.

Examples:

str = String.new("apple").extend Rya::CoreExtensions::String
other = "ppie"

str.longest_common_substring other #=> 2

Parameters:

  • other —

    The other string to test against.



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/rya/core_extensions.rb', line 48

def longest_common_substring other
  if self.empty? || other.empty?
    return 0
  end

  self_len  = self.length
  other_len = other.length

  longest_common_suffix = Object::Array.new(self_len + 1) { Object::Array.new(other_len + 1, 0) }

  len = 0

  (self_len + 1).times do |i|
    (other_len + 1).times do |j|
      if i.zero? || j.zero? # this is for the dummy column
        longest_common_suffix[i][j] = 0
      elsif self[i - 1] == other[j - 1]
        val = longest_common_suffix[i - 1][j - 1] + 1
        longest_common_suffix[i][j] = val

        len = [len, val].max
      else
        longest_common_suffix[i][j] = 0
      end
    end
  end

  len
end