algorithm - 最长公共(public)间隔的快速算法(带重排的 LCS)

Question

假设我们有两个字符流:

S = 1,2,3,5,7,4,4,10,11,12
T = 3,1,2,9,6,4,10,5,9

我想找到这个流的最大子序列，以便通过某种重新排列使它们相同，例如在这种情况下，第一个和 3,1 中的 1,2,3， 2在second stream中，可以通过重排相互转换，看起来是最大的(长度为3)。

O(n^2) 的算法在 Quadratic time algorithms for finding common intervals in two and more sequences 中可用.

任何想法都很好，没有必要改进它，或者如果你有想法证明你的想法。我想使用 is 来解决我的问题，时间复杂度不适合我当前的数据集。

Answer 1

你可以做两件事来让它更快:

1. 确保将它们作为整数而不是字符串进行比较(以防万一您使用的循环算法使用的字符串比较很慢)。

2. 此问题的动态规划方法需要一个大表 (m * n)。递归关系只要求表中的当前行和上一行继续。如果您使用此优化，您只需要 2 * min(m, n) 空间来计算序列。

正如我在 AFAIK 上面的评论中所述，您不能比 O(n * m) 做得更好，对于相同大小的输入，它可以退化为 O(n^2)。这些优化仅有助于比较时间和节省内存(因为正如您所说，在最坏的情况下您需要一个 5000 * 5000 的条目表，这会占用大量内存)。