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