これは、「アルゴリズムの設計と分析の概要」の演習です。文字列の一致の問題です。文字列 ABCD があり、パターン XY があるとします。文字列にパターンが含まれているかどうかを確認したい。
ここでは力ずくの使用を想定しているだけなので、左から右への比較では A と X を比較し、次は B と X を比較します。右から左への比較では B と Y を比較しますが、次は C を比較します。ヒントは、右から左への比較には利点があると言っていますが、その理由はわかりません。
どんなヒントでも大歓迎です！
1833 次
2 に答える
10
はい。
こちらもご覧ください
極端な例として、ABCDテキスト内のパターンを見つける必要があるかどうかを考えてみましょう12345678。
もちろん、最も早い一致はテキストの先頭から始まります。Dパターンを後方に一致させようとするため、テキストの 4 番目の文字と一致するかどうかを確認します。
?
12345678
ABCD
ABCこれは一致ではないため、最初の 3 文字と一致させようとしても意味がないことがわかっています。4また、(線形時間前処理の後で) 見つけた文字がパターンにまったく現れないこともわかっているため、見つけることができる最も早い一致は、次の位置、つまり 5 番目の文字から開始する必要があります。
D再び後方一致を試みるので、8 番目の文字と一致するかどうかを確認します。
?
12345678
ABCD
私たちは見つけます8; これは一致しません。したがって、パターンはテキストには表示されません。テキストから 2 文字だけを表示する必要がありました。
これは、Boyer-Moore アルゴリズムの重要な特徴の 1 つです。長さ のテキストと長さNの固定パターンのM場合、平均ケースのパフォーマンスはN/M比較になります。つまり、最初は直感に反するかもしれませんが、探しているパターンが長ければ長いほど、通常はより速く見つけることができます。
于 2010-06-24T16:40:35.497 に答える
0
Y が B と一致しない場合、次に比較する 2 つの文字は何ですか? これらの手順を繰り返し続けると、文字列全体をカバーする前に何回比較を行うでしょうか? 「ブルートフォース」アプローチと何回比較しますか?
于 2010-06-24T17:13:15.400 に答える