最长公共子线性内存使用情况 [英] longest common subsequence with linear memory usage

问题描述

我试图找到一个算法，使用的内存线性空间为：

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

给定两个串x和y在任意的字母，确定它们的最长公共子序列。

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

推荐答案

请注意，当你计算的动态规划的解决方案来解决LCS问题表的下一行，你只需要previous行和你的当前行。然后，你可以修改动态规划的解决方案来跟踪只有previous行和当前行，而不是MXN表。到达当前行的末尾时，都设置了previous行当前行，并从该行的重新开始。你这样做m次，其中m为你的表中的行数。这将使用空间的线性中的列数

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.

这篇关于最长公共子线性内存使用情况的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！