<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-268

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

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.

<%@ include file="cited.html" %>

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)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>