[KBK], [PYK]: The '''longest common subsequence]''' is:

Given two lists L1 and L2, compute the largest set of ordered pairs 
    {x1,y1), (x2,y2), ..., (xn, yn)
such that
    x1 < x2 < ... < xn
    y1 < y2 < ... < yn
and
    L1[x1] = L2[y1] ; L1[x2] = L2[y2] ; ... L1[xn] = L2[yn]

In contrast with [longest common substring], the resulting ordered pairs are
not necessarily contiguous.
[longest common subsequence: folklore algorithm] is one Tcl implementation of the
"folklore algorithm." 

Hunt and McIlroy have published a much better algorithm (used in the Unix 'diff' command) that is implemented at [diff in Tcl].  This page is here to hold some of the historical discussion.

<<categories>> algorithm | string processing