最长公共子串算法O(n*m)暴力破解
最长公共子串算法O(n*m)暴力破解
提问于 2012-10-15 13:24:24
我在看http://en.wikipedia.org/wiki/Longest_common_substring_problem上的算法
它们使用动态编程，这为它们提供了O(nm)的时间。然而，用蛮力算法不能达到同样的时间复杂度吗？我正在做一个作业题，在O(n*m)时间内找到这个算法，其中n和m是字符串长度。
对于字符串A和字符串B，我检查Ai是否等于B中的任何元素。如果它等于某个Bj，则检查Ai +1是否等于Bj + 1，如果Ai +2= Bi +2，依此类推，直到不再匹配或字符串结束。如果是不匹配的情况，那么从我们在B中检查的最后一个元素开始，继续检查B中的Ai。我们对每个A元素重复这个过程，同时存储到目前为止找到的最大子串的开始和结束索引。该算法似乎是O(n*m)。如果我没有弄错的话，有什么理由不使用这种方法吗？
谢谢你的帮助。
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-10-15 13:42:20
如果我没有读错你的算法，那么我相信它是错误的。
让A = "abac"和B = "ababac"。然后，使用i = 0，我们可以看到字符串在j = 0处匹配。所以我们开始匹配，从b != c开始在j = 3失败。因此，我们从j = 3开始匹配，但从b != a开始立即失败(请注意，我们没有从j = 2开始，因为我们在那里成功地匹配了a = a )。然后我们会得出结论，最长的子串是aba，这是不正确的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12889727
复制相关文章
相似问题
腾讯云开发者
