Algorithms for the Longest Common Subsequence Problem

Abstract

AaS~ACT Two algorithms are presented that solve the longest common subsequence problem The first algorithm is applicable in the general case and requires O(pn + n log n) time where p is the length of the longest common subsequence The second algorithm requires time bounded by O(p(m + 1 -p)log n) In the common speoal case where p is close to m, this algorithm takes much less time than n ~