| A fast algorithm for computing longest common subsequences |
| Full text |
 Pdf
(391 KB)
|
Source
|
Communications of the ACM
archive
Volume 20 , Issue 5 (May 1977)
table of contents
Pages: 350 - 353
Year of Publication: 1977
ISSN:0001-0782
|
|
Authors
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 77, Downloads (12 Months): 391, Citation Count: 59
|
|
|
 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(n2). 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(n2 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
van Emde Boas, P. Preserving order in a forest in less than logarithmic time. 16th Annual Symp. on Foundations Comptr. Sci., Oct. 1975, pp. 75-84.
|
| |
3
|
Fredman, M.L. On computing the length of longest increasing subsequences. Discrete Mathematics 11, 1 (Jan. 1975), 29-35.
|
 |
4
|
|
| |
5
|
Szymansld, T.G. A special case of the maximal common subsequence problem. TR-170, Dep. Electrical Eng., Princeton U., Princeton, N.J., Jan. 1975.
|
| |
6
|
|
| |
7
|
Yao, A.C. and Yao, F.F. On computing the rank function for a set of vectors. UIUCDCS-R-75-699, Dep. Comptr. Sci., U. of Illinois at Urbana-Champaign, Urbana, Ill., Feb. 1975.
|
CITED BY 60
|
|
|
|
|
Xiaoping Tang , Ruiqi Tian , D. F. Wong, Fast evaluation of sequence pair in block placement by longest common subsequence computation, Proceedings of the conference on Design, automation and test in Europe, p.106-111, March 27-30, 2000, Paris, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
David Eppstein , Zvi Galil , Raffaele Giancarlo , Giuseppe F. Italiano, Sparse dynamic programming, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.513-522, January 22-24, 1990, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
James R. Cordy , Thomas R. Dean , Nikita Synytskyy, Practical language-independent detection of near-miss clones, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.1-12, October 04-07, 2004, Markham, Ontario, Canada
|
|
|
|
|
|
|
|
|
Michael H. Albert , Alexander Golynski , Angèle M. Hamel , Alejandro López-Ortiz , S. Srinivasa Rao , Mohammad Ali Safari, Longest increasing subsequences in sliding windows, Theoretical Computer Science, v.321 n.2-3, p.405-414, 16 August 2004
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Suratna Budalakoti , Ashok N. Srivastava , Matthew E. Otey, Anomaly detection and diagnosis algorithms for discrete symbol sequences with applications to airline safety, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, v.39 n.1, p.101-113, January 2009
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
