def __lcs(a, b)
a_start = b_start = 0
a_finish = a.size - 1
b_finish = b.size - 1
vector = []
while (a_start <= a_finish) and
(b_start <= b_finish) and
(a[a_start] == b[b_start])
vector[a_start] = b_start
a_start += 1
b_start += 1
end
while (a_start <= a_finish) and
(b_start <= b_finish) and
(a[a_finish] == b[b_finish])
vector[a_finish] = b_finish
a_finish -= 1
b_finish -= 1
end
b_matches = Diff::LCS.__position_hash(b, b_start .. b_finish)
thresh = []
links = []
(a_start .. a_finish).each do |ii|
ai = a.kind_of?(String) ? a[ii, 1] : a[ii]
bm = b_matches[ai]
kk = nil
bm.reverse_each do |jj|
if kk and (thresh[kk] > jj) and (thresh[kk - 1] < jj)
thresh[kk] = jj
else
kk = Diff::LCS.__replace_next_larger(thresh, jj, kk)
end
links[kk] = [ (kk > 0) ? links[kk - 1] : nil, ii, jj ] unless kk.nil?
end
end
unless thresh.empty?
link = links[thresh.size - 1]
while not link.nil?
vector[link[1]] = link[2]
link = link[0]
end
end
vector
end