longest common subsequence

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.