隨機圖案匹配

Question

我有一個問題與一個exercie。我希望你能幫助我。

我們想要檢測長度爲m的二進制模式P是否出現在長度爲n的二進制文本T中，其中：m < n。

陳述一個運算時間爲O（n）的算法，我們假設對O（log2 n）位數的算術運算可以在恆定的時間內執行。當P是T的子串時，該算法應該以概率1接受，否則以至少1-1/n的概率拒絕。

我們得到了一個暗示，我們應該使用指紋識別。有人可以幫忙嗎？ 謝謝！

Answer 1

KMP是一種確定性算法，可在線性時間內完成此操作。 但我也想知道，如果這可以用概率算法來完成。