longest common subsequence with linear memory usage [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

I'm trying to find an algorithm which uses linear space of memory for:

Given two strings x and y over an arbitrary alphabet, determine their longest common sub sequence.

Answer 1

Note that when you're calculating the next row of the table in the dynamic programming solution to solve the LCS problem, you only need the previous row and your current row. Then you can modify the dynamic programming solution to keep track of only the previous row and the current row instead of the m x n table. Every time you reach the end of the current row, you set the previous row to the current row, and start from the beginning of the row again. You do this m times where m is the number of rows in your table. This will use space linear in the number of columns.