Fast Algorithm For The Longest-Common-Subsequence Problem
Abbreviated Journal Title
Computer Science; Information Systems
In this paper, a fast algorithm for the longest-common-subsequence problem is presented which runs in O((p + n)log n), time where p is the total number of pairs of matched positions between the strings. Thus, the average performance of this algorithm is much better than those of the quadratic algorithms proposed earlier and takes only a linear amount of space.
Mukhopadhyay, Amar, "Fast Algorithm For The Longest-Common-Subsequence Problem" (1980). Faculty Bibliography 1980s. 28.