A fast algorithm for computing longest common subsequences

I just purchased this paper from the ACM or ten dollars.  It was written in 1977 yet there are still no copies of it available for free download.

It’s amazingly annoying to have to pay for content like this especially when it’s research material.  The ACM doesn’t own copyright on this paper and it’s just slowing down computer science to lock it up behind a paywall.

If the NY Times can drop their paywall then so can the ACM!

Here’s the abstract of 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(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.

… which is now liberated from the ACM for all time.  I wonder how long before it turns up as the first result in Google?



%d bloggers like this: