algorithm - 随机模式匹配

Question

我的练习有问题。我希望你能帮助我。

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

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

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

Answer 1

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