Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

A fast algorithm for computing longest common subsequences

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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Communications of the ACM Association for Computing Machinery

A fast algorithm for computing longest common subsequences

Loading next page...
 
/lp/association-for-computing-machinery/a-fast-algorithm-for-computing-longest-common-subsequences-jKZrfNhu77

References (10)

Publisher
Association for Computing Machinery
Copyright
Copyright © 1977 by ACM Inc.
ISSN
0001-0782
DOI
10.1145/359581.359603
Publisher site
See Article on Publisher Site

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.

Journal

Communications of the ACMAssociation for Computing Machinery

Published: May 1, 1977

There are no references for this article.