Research Report CS-RR-268

M.S. Paterson and Vlado Dancik, Longest Common Subsequences (May 1, 1994).

Abstract

The length of a longest common subsequence (LLCS) of two or more strings is a useful measure of their similarity. The LLCS of a pair of strings is related to the 'edit distance', or number of mutations/errors/editing steps required in passing from one string to the other. In this talk, we explore some of the combinatorial properties of the sub- and super-sequence relations, survey various algorithms for computing the LLCS, and introduce some results on the expected LLCS for pairs of random strings.

Citation

This report has since been published elsewehere and is no longer available as a research report from Warwick. The published paper may be cited as:

Mike Paterson and Vlado Dancik, "Longest Common Subsequences", Mathematical Foundations of Computer Science 1994, Lecture Notes in Computer Science 841, ed. Igor Privara, Branislav Rovan and Peter Ruzicka, Springer-Verlag, pp. 127-142 (1994)