Compute differences using the McIlroy-Hunt LCS algorithm
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Compute differences using the McIlroy-Hunt LCS algorithm.


Diff::LCS is a port of Perl's Algorithm::Diff that uses the McIlroy-Hunt longest common subsequence (LCS) algorithm to compute intelligent differences between two sequenced enumerable containers.

The implementation is based on Mario I. Wolczko's Smalltalk version (1.2, 1993) and Ned Konz's Perl version (Algorithm::Diff).

How to use

Using this module is quite simple. By default, Diff::LCS does not extend objects with the Diff::LCS interface, but will be called as if it were a function:

require 'diff/lcs'

seq1 = %w(a b c e h j l m n p)
seq2 = %w(b c d e f j k l m r s t)

lcs = Diff::LCS.LCS(seq1, seq2)
diffs = Diff::LCS.diff(seq1, seq2)
sdiff = Diff::LCS.sdiff(seq1, seq2)
seq = Diff::LCS.traverse_sequences(seq1, seq2, callback_obj)
bal = Diff::LCS.traverse_balanced(seq1, seq2, callback_obj)
seq2 == Diff::LCS.patch!(seq1, diffs)
seq1 == Diff::LCS.unpatch!(seq2, diffs)
seq2 == Diff::LCS.patch!(seq1, sdiff)
seq1 == Diff::LCS.unpatch!(seq2, sdiff)

Objects can be extended with Diff::LCS:

lcs = seq1.lcs(seq2)
diffs = seq1.diff(seq2)
sdiff = seq1.sdiff(seq2)
seq = seq1.traverse_sequences(seq2, callback_obj)
bal = seq1.traverse_balanced(seq2, callback_obj)
seq2 == seq1.patch!(diffs)
seq1 == seq2.unpatch!(diffs)
seq2 == seq1.patch!(sdiff)
seq1 == seq2.unpatch!(sdiff)

By requiring diff/lcs/array or diff/lcs/string, Array or String will be extended for use this way.


Original author: Austin Ziegler.


  • Alan Chen
  • Gioele Barabucci


Copyright 2004 Austin Ziegler

This program is free software. It may be redistributed and/or modified under the terms of the GPL version 2 (or later), the Perl Artistic licence, or the Ruby licence.

Implements McIlroy-Hunt diff algorithm; adapted from:

  • Perl's Algorithm::Diff by Ned Konz
  • Smalltalk by Mario I. Wolczko