This vocabulary provides words for three apparently unrelated but in fact very similar problems: finding a longest common subsequence between two sequences, getting a minimal edit script (diff) between two sequences, and calculating the Levenshtein distance between two sequences. The implementations of these algorithms are very closely related, and all running times are O(nm), where n and m are the lengths of the input sequences.

lcs ( seq1 seq2 -- lcs )

lcs-diff ( old new -- diff )

levenshtein ( old new -- n )

The lcs-diff word returns a sequence of tuples of the following classes. They all hold their contents in the 'item' slot.

insert

delete

retain