-
Notifications
You must be signed in to change notification settings - Fork 0
/
lcs.cr
67 lines (59 loc) · 1.92 KB
/
lcs.cr
1
2
3
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
38
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
require "./util"
module K8S::Hashdiff
# caculate array difference using LCS algorithm
# http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
# ameba:disable Metrics/CyclomaticComplexity
def lcs(arraya, arrayb, **options) : Array(Tuple(Int32, Int32))
return Array(Tuple(Int32, Int32)).new if arraya.empty? || arrayb.empty?
opts = {similarity: 0.8, prefix: ""}
.merge(options)
opts = opts.merge({
prefix: prefix_append_array_index(**opts, array_index: "*"),
})
a_start = b_start = 0
a_finish = arraya.size - 1
b_finish = arrayb.size - 1
vector = Array(Tuple(Int32, Int32)).new
lcs = Array(Array(Tuple(Symbol, Int32))).new
(b_start..b_finish).each do |bi|
lcs.insert(bi, Array(Tuple(Symbol, Int32)).new)
(a_start..a_finish).each do |ai|
if similar?(arraya[ai], arrayb[bi], **opts)
topleft = (ai > 0) && (bi > 0) ? lcs[bi - 1][ai - 1][1].as(Int32) : 0
lcs[bi].insert(ai, {:topleft, topleft + 1})
elsif (top = bi > 0 ? lcs[bi - 1][ai][1] : 0)
left = ai > 0 ? lcs[bi][ai - 1][1].as(Int32) : 0
count = top > left ? top : left
direction = if top > left
:top
elsif top < left
:left
elsif bi.zero?
:top
elsif ai.zero?
:left
else
:both
end
lcs[bi].insert(ai, {direction, count})
end
end
end
x = a_finish
y = b_finish
while (x >= 0) && (y >= 0) && (lcs[y][x][1] > 0)
if lcs[y][x][0] == :both
x -= 1
elsif lcs[y][x][0] == :topleft
vector.insert(0, {x, y})
x -= 1
y -= 1
elsif lcs[y][x][0] == :top
y -= 1
elsif lcs[y][x][0] == :left
x -= 1
end
end
vector
end
end