1

我正在查看http://en.wikipedia.org/wiki/Longest_common_substring_problem上的算法

他们使用动态编程，这给了他们 O(nm) 的时间。但是，用蛮力算法不能实现相同的时间复杂度吗？我正在做一个家庭作业问题，在 O(n*m) 时间内找到这个算法，其中 n 和 m 是字符串长度。

对于字符串 A 和字符串 B，我检查 A[i] 是否等于 B 中的任何元素。如果它确实等于某个 B[j]，则检查 A[i + 1] 是否等于 B[j + 1]，然后如果 A[i + 2] = in B[i + 2] 依此类推，直到不再有匹配或字符串结尾。如果是不匹配的情况，则从我们在 B 中检查的最后一个元素开始继续检查 B 中的 A[i]。我们对每个 A 元素重复此过程，同时存储到目前为止找到的最大子字符串的开始和结束索引. 该算法似乎是 O(n*m)。如果我对此没有错，是否有任何理由不使用这种方法？

谢谢你的帮助。

4

1 回答 1

2

如果我正确阅读了您的算法，那么我认为这是错误的。

让A = "abac"和B = "ababac"。然后，i = 0我们看到字符串在 处匹配j = 0。j = 3所以我们开始匹配，并在since失败b != c。所以我们从 开始匹配j = 3，但从那以后立即失败b != a（请注意，我们不是从那里开始匹配，j = 2因为我们在那里成功匹配a = a）。然后我们会得出结论，最长的子串是aba，这是不正确的。

于 2012-10-15T05:42:19.680 回答