Longest Common Subsequence

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).

Parameters

$n$ : length of the longer input string
$m$ : length of the shorter input string
$r$ : length of the LCS
$s$ : size of the alphabet
$p$ : the number of dominant matches (AKA number of minimal candidates), i.e. the total number of ordered pairs of positions at which the two sequences match

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 15 of 15 algorithms


Rick (Algorithm 2)	1995	$O(sn + \min(r(n - r), rm))$	$O(sn + p)$
Rick (Section 4)	1995	$O(sn + \min(sp, rm))$	$O(sn + p)$
Chin and Poon	1991	$O(sn + \min(sp, rm))$	$O(p + n)$
Wu et al.	1990	$O(n(m-r))$	$O(m^2)$
Kuo and Cross	1989	$O(p + n(r+\log n))$	$O(p + n)$
Apostolico and Guerra (HS1 Algorithm)	1987	$O(m \log n +p \log(2mn/p))$	$O(p + n)$
Apostolico and Guerra (Algorithm 2)	1987	$O(rm + sn + n \log s)$	$O(p + sn)$
Miller and Myers	1985	$O(n(m-r))$	$O(m^2)$
Hsu and Du (Scheme 2)	1984	$O(rm \log(n/r) + rm)$	$O(rm)$
Hsu and Du (Scheme 1)	1984	$O(rm \log(n/m) + rm)$	$O(rm)$
Nakatsu et al.	1982	$O(n(m-r))$	$O(m^2)$
Mukhopadhyay	1980	$O((n + p) \log n)$	$O(p + n)$
Hunt and Szymanski	1977	$O((n + p) \log n)$	$O(p + n)$
Hirschberg	1977	$O(rn + n \log n)$	$O(n + p)$
Wagner and Fischer	1974	$O(mn)$	$O(mn)$

Reductions Table

Displaying 2 of 2 reductions

			See more
Most OV	Longest Common Subsequence	2015
Unbalanced OV	Longest Common Subsequence	2015

Other relevant algorithms

Insuffient Data to display table