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] と等しいかどうかを確認します。 if 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 = 3sinceで失敗しb != cます。したがって、 でマッチングを開始しますj = 3が、すぐに失敗します(そこでマッチングに成功したため、 でb != a開始しないことに注意してください)。次に、最長の部分文字列は であると結論付けますが、これは正しくありません。j = 2a = aaba

于 2012-10-15T05:42:19.680 に答える