Thumbnail
Access Restriction
Subscribed

Author Hunt, James W. ♦ Szymanski, Thomas G.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Longest common subsequence ♦ Efficient algorithms
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.
Description Affiliation: Princeton Univ., Princeton, NJ (Szymanski, Thomas G.) || Stanford Univ., Stanford, CA (Hunt, James W.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 5
Page Count 4
Starting Page 350
Ending Page 353


Open content in new tab

   Open content in new tab
Source: ACM Digital Library