最长公共子串的这种方法是否正确？

我找到了一个算法Longest Common Substring。通常使用dynamic programming，使用尺寸为mxn的2-D数组完成，其中m和n是所考虑的两个串的长度。最长公共子串的这种方法是否正确？

我将为这两个字符串构造以下矩阵。

M[i][j] = 1 if s1[i]==s2[j] else 0.

例如，如果字符串是：abcxy和pqaabx

矩阵如下所示：

a b c x y 
p 0 0 0 0 0 
q 0 0 0 0 0 
a 1 0 0 0 0 
a 1 0 0 0 0 
b 0 1 0 0 0 
x 0 0 0 1 0

现在，我寻找在1秒的最大连续序列每个对角线在左上方到右下方向。

其中的最大值将是答案。

我可以执行上面的操作，而不明确使用数组。时间复杂度仍然是O(M*N)。所以，不需要记忆。

任何人都可以指出我哪里错了吗？

来源

2014-02-27 nitish712

看起来不错，我有什么理由认为这是不正确的吗？ –

@PeterdeRivaz如果这是正确的，那么为什么[wikipedia]（http://en.wikipedia.org/wiki/Longest_common_substring_problem）使用一种使用额外内存的算法？另外，我没有找到任何具有“O（MN）”复杂性并且没有额外内存的解决方案。 – nitish712

你的方法是正确的。为证明假设S1和S2的最长公共子串来自S1 [i..j]和S2 [p..q]。这意味着 S1 [i + k] = S2 [p + k]

这些都位于从（i，p）开始的对角线上。

动态编程解决方案做的是同样的事情，但不是先计算表格，然后通过对角线路径计算表格，这取决于它的对角线父母加上它们是否匹配。

EDITED

在使用额外的内存维基百科解决您的评论。这只是为了清楚。原则上，您只需要维基百科解决方案中的两行矩阵，并将当前最大计数保存在一个变量中。这是正确的，因为对于矩阵中的任何（i，j）条目，如果s1 [i] = s2 [j（i，j））， ]）

正如您所看到的，当前行元素仅取决于紧靠上一行的元素。

来源

2014-02-27 14:04:33 sukunrt

你的算法是正确的，但标准的DP方法消除了你的第二阶段，并使解决方案更简单。

除了标记布尔值，然后扫描对角线寻找最长的序列，您可以在构建矩阵时计算对角线长度 - 只需要一次通过。

在时间和空间复杂度方面，两种解决方案都是O（NxM）。如果您使用位矩阵表示，您的解决方案可以节省一些内存，而另一种解决方案可能稍微快一点。

来源

2014-02-27 15:05:17

我其实不想使用矩阵。我强调，同样的操作也可以在没有矩阵的情况下完成。我的意思是使用两个'循环' – nitish712

@ nitish712：实际上你是对的，你可以使用只有恒定的额外空间和O（NxM）时间。但请注意，维基百科页面并未建议使用什么数据结构 - 它仅使用表格描述递归过程。 –

最长公共子串的这种方法是否正确？

回答

相关问题