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] と等しいかどうかを確認します。 if A[i + 2] = in B[i + 2] というように、一致しなくなるか文字列の終わりまで続きます。一致しない場合は、B で最後にチェックした要素から始めて、B で A[i] のチェックを続けます。これまでに見つかった最大部分文字列の開始インデックスと終了インデックスを保存しながら、すべての A 要素に対してこのプロセスを繰り返します。 . このアルゴリズムは O(n*m) のようです。私がこれについて間違っていなければ、このアプローチが使用されない理由はありますか?
助けてくれてありがとう。