最長公共子算法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。所以我們開始匹配，並且從b != c開始在j = 3處失敗。所以我們從j = 3開始匹配，但自b != a以後立即失敗（請注意，我們並非從j = 2開始，因爲我們在那裏成功匹配a = a）。然後我們會得出最長的子字符串aba，這是不正確的。