A Fast Algorithm for Computing Longest Common Subsequences

Previously published algorithms for finding
the longest common subsequence of two sequences 
of length n have had a best-case running time of O(n^2).
 An algorithm for this problem is presented 
which has a running time of O((r + n)log n), where r
is the total number of ordered pairs of positions 
at which the two sequences match.  Thus in the worst
case the algorithm has a running time of O(n^2 log 
n).  However, for those applications where most positions
of one sequence match relatively few positions 
in the other sequence, a running time of O(n log n) can be expected.

CACM May, 1977

Hunt, J. W.
Szymanski, T. G.

Longest common subsequence, efficient algorithms

3.73 3.63 5.25

CA770509 JB December 29, 1977  1:46 AM

2963	4	2963
3114	4	2963
2745	5	2963
2963	5	2963
2963	5	2963
2963	5	2963