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.