Longest Common Subsequence

time-complexity dynamic-programming lcs
tsudot picture tsudot · Jun 9, 2010 · Viewed 12.1k times · Source

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.

Answer

j_random_hacker picture j_random_hacker · Sep 10, 2010

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.

Related questions

Find common substring between two strings

I'd like to compare 2 strings and keep the matched, splitting off where the comparison fails. So if I have 2 strings - string1 = apples string2 = appleses answer = apples Another example, as the string could have more than one word. string1 = apple …

Read More
Given a list of numbers and a number k, return whether any two numbers from the list add up to k

This question was asked in the Google programming interview. I thought of two approaches for the same: Find all the subsequences of length. While doing so compute the sum and of the two elements and check if it is equal …

Read More
Memoization or Tabulation approach for Dynamic programming

There are many problems that can be solved using Dynamic programming e.g. Longest increasing subsequence. This problem can be solved by using 2 approaches Memoization (Top Down) - Using recursion to solve the sub-problem and storing the result in some …

Read More