エクササイズに問題があります。あなたが私を助けてくれることを願っています。
長さmのバイナリパターンPが長さnのバイナリテキストTで発生するかどうかを検出する必要があります。ここで、m<nです。
時間O(n)で実行されるアルゴリズムを記述します。ここで、O(log2 n)ビット数の算術演算は一定時間で実行できると想定しています。アルゴリズムは、PがTのサブストリングである場合は常に確率1で受け入れ、それ以外の場合は少なくとも1〜1/nの確率で拒否する必要があります。
フィンガープリントを使用する必要があるというヒントが得られました。誰かが助けることができますか?ありがとう!