Rosetta Code

Longest common subsequence: Difference between revisions

← Older editNewer edit →
Content deleted Content added
CNHume (talk | contribs)
159 edits
m Added citation for Claus Rick 2000
CNHume (talk | contribs)
159 edits
m Adjusted References, emphasizing the priority of Claus Rick.
Line 389:
A binary search optimization due to Hunt and Szymanski can be applied in this case, which results in expected performance of O(n log m), given m <= n. In the worst case, performance degrades to O(m*n log m) time if the number of matches, and the space required to represent them, should grow to O(m*n).
 
More recent improvements byClaus Rick andhas byalso Goemandescribed anda Clausenlinear-space reducealgorithm thewith a time bound toof O(n*s + min(p*m, p*(n-p))), where the alphabet is of size s and the LCS is of length p.
 
'''References'''
Line 404:
by James W. Hunt and Thomas G. Szymanski, published May 1977<br />
Communications of the ACM [Volume 20, Number 5, pp. 350-353]
 
"A new flexible algorithm for the longest common subsequence problem"<br />
by Claus Rick, published 1995, Proceedings, 6th Annual Symposium on<br />
Combinatorial Pattern Matching [Lecture Notes in Computer Science,<br />
Springer Verlag, Volume 937, pp. 340-351]
 
"A New Practical Linear Space Algorithm for the Longest Common<br />
Subsequence Problem" by Heiko Goeman and Michael Clausen,<br />
published 2002, Kybernetika [Volume 38, Issue 1, pp. 45-66]
 
"Simple and fast linear space computation of longest common subsequences"<br />
Retrieved from "https://rosettacode.org/wiki/Longest_common_subsequence"