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. CACM May, 1977 Hunt, J. W. Szymanski, T. G. Longest common subsequence, efficient algorithms 3.73 3.63 5.25 CA770509 JB December 29, 1977 1:46 AM 2963 4 2963 3114 4 2963 2745 5 2963 2963 5 2963 2963 5 2963 2963 5 2963