Fast Algorithm For The Longest-Common-Subsequence Problem

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