algorithm - 最长公共(public)子串算法 O(n*m) 蛮力

Question

我正在查看 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)。如果我对此没有错，是否有任何理由不使用这种方法？

感谢您的帮助。

Answer 1

如果我正确阅读了您的算法，那么我相信它是错误的。

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