随机图案匹配

Question

我有一个问题与一个exercie。我希望你能帮助我。

我们想要检测长度为m的二进制模式P是否出现在长度为n的二进制文本T中，其中：m < n。

陈述一个运算时间为O（n）的算法，我们假设对O（log2 n）位数的算术运算可以在恒定的时间内执行。当P是T的子串时，该算法应该以概率1接受，否则以至少1-1/n的概率拒绝。

我们得到了一个暗示，我们应该使用指纹识别。有人可以帮忙吗？ 谢谢！

Answer 1

KMP是一种确定性算法，可在线性时间内完成此操作。 但我也想知道，如果这可以用概率算法来完成。