-2

エクササイズに問題があります。あなたが私を助けてくれることを願っています。

長さmのバイナリパターンPが長さnのバイナリテキストTで発生するかどうかを検出する必要があります。ここで、m<nです。

時間O(n)で実行されるアルゴリズムを記述します。ここで、O(log2 n)ビット数の算術演算は一定時間で実行できると想定しています。アルゴリズムは、PがTのサブストリングである場合は常に確率1で受け入れ、それ以外の場合は少なくとも1〜1/nの確率で拒否する必要があります。

フィンガープリントを使用する必要があるというヒントが得られました。誰かが助けることができますか?ありがとう!

4

1 に答える 1

0

KMPは、線形時間でこれを行う決定論的アルゴリズムです。しかし、これが確率的アルゴリズムで実行できるかどうかも疑問に思っています。

于 2012-05-06T16:19:39.617 に答える