# File lib/diff/lcs.rb, line 816
816:     def __lcs(a, b)
817:       a_start = b_start = 0
818:       a_finish = a.size - 1
819:       b_finish = b.size - 1
820:       vector = []
821: 
822:         # Prune off any common elements at the beginning...
823:       while (a_start <= a_finish) and
824:             (b_start <= b_finish) and
825:             (a[a_start] == b[b_start])
826:         vector[a_start] = b_start
827:         a_start += 1
828:         b_start += 1
829:       end
830: 
831:         # Now the end...
832:       while (a_start <= a_finish) and
833:             (b_start <= b_finish) and
834:             (a[a_finish] == b[b_finish])
835:         vector[a_finish] = b_finish
836:         a_finish -= 1
837:         b_finish -= 1
838:       end
839: 
840:         # Now, compute the equivalence classes of positions of elements.
841:       b_matches = Diff::LCS.__position_hash(b, b_start .. b_finish)
842: 
843:       thresh = []
844:       links = []
845: 
846:       (a_start .. a_finish).each do |ii|
847:         ai = a.kind_of?(String) ? a[ii, 1] : a[ii]
848:         bm = b_matches[ai]
849:         kk = nil
850:         bm.reverse_each do |jj|
851:           if kk and (thresh[kk] > jj) and (thresh[kk - 1] < jj)
852:             thresh[kk] = jj
853:           else
854:             kk = Diff::LCS.__replace_next_larger(thresh, jj, kk)
855:           end
856:           links[kk] = [ (kk > 0) ? links[kk - 1] : nil, ii, jj ] unless kk.nil?
857:         end
858:       end
859: 
860:       unless thresh.empty?
861:         link = links[thresh.size - 1]
862:         while not link.nil?
863:           vector[link[1]] = link[2]
864:           link = link[0]
865:         end
866:       end
867: 
868:       vector
869:     end