Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Longest Common Subsequence

Consider 2 sequences X[1..m] and Y[1..n]. The memoization algorithm would compute the LCS in time O(m*n). Is there any better algorithm to find out LCS wrt time? I guess memoization done diagonally can give us O(min(m,n)) time complexity.

like image 964
tsudot Avatar asked Jun 09 '10 05:06

tsudot


1 Answers

Gene Myers in 1986 came up with a very nice algorithm for this, described here: An O(ND) Difference Algorithm and Its Variations.

This algorithm takes time proportional to the edit distance between sequences, so it is much faster when the difference is small. It works by looping over all possible edit distances, starting from 0, until it finds a distance for which an edit script (in some ways the dual of an LCS) can be constructed. This means that you can "bail out early" if the difference grows above some threshold, which is sometimes convenient.

I believe this algorithm is still used in many diff implementations.

like image 169
j_random_hacker Avatar answered Sep 18 '22 13:09

j_random_hacker