Module: RubyFish::LongestSubstring

Defined in:
lib/rubyfish/longest_substring.rb

Class Method Summary collapse

Class Method Details

.distance(a, b, opts = {}) ⇒ Object

en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring#Ruby



4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/rubyfish/longest_substring.rb', line 4

def distance a, b, opts={}
	ignore_case = opts[:ignore_case]
	
  as = a.to_s
  bs = b.to_s
  
  if ignore_case
  	as.downcase!
  	bs.downcase!
  end

  rows = as.size
  cols = bs.size

  if rows == 0 || cols == 0
    return 0
  end

  num= ::RubyFish::MMatrix.new rows, cols
  len,ans=0

  as.each_char.with_index do |ac, i|
    bs.each_char.with_index do |bc, j|
      unless ac == bc
        num[i, j]=0
      else
        (i==0 || j==0)? num[i, j] = 1 : num[i, j] = 1 + num[i-1, j-1]
        len = ans = num[i, j] if num[i, j] > len
      end
    end
  end

  ans
end

.longest_substring(a, b, opts = {}) ⇒ Object 



39
40
41
42
43
44
45
46
47
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
77
78
79
80
81
82
83
84
85
 
# File 'lib/rubyfish/longest_substring.rb', line 39

def longest_substring a, b, opts={}
	ignore_case = opts[:ignore_case]
	
  as = a.to_s
  bs = b.to_s
  
  if ignore_case
  	as.downcase!
  	bs.downcase!
  end

  rows = as.size
  cols = bs.size

  res = ""
  len = 0
  last_sub = 0

  if rows == 0 || cols == 0
    return res
  end

  num = ::RubyFish::MMatrix.new rows, cols

  as.each_char.with_index do |ac, i|
    bs.each_char.with_index do |bc, j|
      unless ac == bc
        num[i, j] = 0
      else
        (i == 0 || j == 0)? num[i, j] = 1 : num[i, j] = 1 + num[i-1, j-1]
        if num[i, j] > len
          len = num[i, j]
          this_sub = i
          this_sub -= num[i-1, j-1] unless num[i-1, j-1].nil?
          if last_sub == this_sub
            res += as[i,1]
          else
            last_sub = this_sub
            res = as[last_sub, (i+1) - last_sub]
          end
        end
      end
    end
  end

  res
end

.longest_substring_index(a, b, opts = {}) ⇒ Object 



87
88
89
 
# File 'lib/rubyfish/longest_substring.rb', line 87

def longest_substring_index(a, b, opts={})
  a.index(longest_substring(a, b, :ignore_case => opts[:ignore_case]))
end