Ax unnecessary calls

halostatue · Dec 19, 2021 · 334b12e · 334b12e
1 parent cd4b76d
commit 334b12e
Showing 1 changed file with 3 additions and 7 deletions.
diff --git a/lib/diff/lcs/internals.rb b/lib/diff/lcs/internals.rb
@@ -44,13 +44,12 @@ def lcs(a, b)
     b_finish = b.size - 1
     vector = []
 
-    # Prune off any common elements at the beginning...
+    # Collect any common elements at the beginning...
     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
-    b_start = a_start
 
     # Now the end...
     while (a_start <= a_finish) and (b_start <= b_finish) and (a[a_finish] == b[b_finish])
@@ -60,6 +59,7 @@ def lcs(a, b)
     end
 
     # Now, compute the equivalence classes of positions of elements.
+    # An explanation for how this works: https://codeforces.com/topic/92191
     b_matches = position_hash(b, b_start..b_finish)
 
     thresh = []
@@ -71,11 +71,7 @@ def lcs(a, b)
       bm = b_matches[ai]
       k = nil
       bm.reverse_each do |j|
-        if k and (thresh[k] > j) and (thresh[k - 1] < j)
-          thresh[k] = j
-        else
-          k = replace_next_larger(thresh, j, k)
-        end
+        k = replace_next_larger(thresh, j)
         links[k] = [k.positive? ? links[k - 1] : nil, i, j] unless k.nil?
       end
     end