A fast algorithm for computing longest common subsequences
- 1 May 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 20 (5), 350-353
- https://doi.org/10.1145/359581.359603
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- On computing the length of longest increasing subsequencesDiscrete Mathematics, 1975
- Preserving order in a forest in less than logarithmic timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975
- The String-to-String Correction ProblemJournal of the ACM, 1974