这个方法的最常见的substring正确的吗？

Question

我已经找到了一种算法 最常见的字符串.它通常是使用 dynamic programming, 使用2-D列大小 mxn 哪里 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

现在，我搜索的最大连续的序列 1s在每一个角这是在左上到底正确的方向。

最大值之中这些将是答案。

我可以执行上述的操作而没有使用列明确。时间复杂性还是 O(M*N).因此，没有必要的记忆。

任何人都可以告诉我我在哪里错了吗？

Answer 1

你的方法是正确的。为证明假设的最常见的substring为S1和S2是从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])

正如你可以看到流行的元素，仅仅依赖的要素在立即上行。

Answer 2

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

而不是标记布尔的价值，然后扫描的对角线以寻找最长的序列，可以计算的对角线的长度为你建立矩阵-只有一个通是必需的。

在时间和空间的复杂性，这两种解决方案是O(n x m).你的解决方案可以节省一些记忆，如果你使用一点矩阵表示，虽然其他的解决办法可能是稍微加快。