algorithm - 这种最长公共(public)子串的方法是否正确？

Question

我找到了 Longest Common Substring 的算法.它通常使用 动态规划 完成，使用大小为 mxn 的二维数组，其中 m 和 n 是正在考虑的两个字符串的长度。

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

M[i][j] = 1 如果 s1[i]==s2[j] 否则 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)。因此，不需要内存。

谁能指出我哪里出错了？

Answer 1

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

这些都位于从 (i,p) 开始的对角线上。

动态规划解决方案做同样的事情，但不是首先计算表并通过对角线路径，而是根据它的对角父级加上它们是否匹配来计算表。

已编辑

关于您对使用额外内存的维基百科解决方案的评论。它只是为了清楚起见。原则上，您只需要维基百科解决方案中的两行矩阵，并将当前最大计数保留在一个变量中。这是正确的，因为对于矩阵中的任何第 (i,j) 个条目

M(i,j) = 1 + M(i-1, j-1)(如果 s1[i] == s2[j])

如您所见，当前行元素仅依赖于紧靠上一行的元素。