Randomized Pattern Matching

Question

I have a problem with an exercie. I hope you can help me.

We want to detect whether a binary pattern P of length m occurs in a binary text T of length n where: m < n.

State an algorithm that runs in time O(n) where we assume that arithmetic operations on O(log2 n) bit numbers can be executed in constant time. The algorithm should accept with probability 1 whenever P is a substring of T and reject with probability at least 1 - 1/n otherwise.

We got a hint that we should use fingerprinting. Can someone help? Thanks!

Answer 1

The KMP is a deterministic algorithm that does this in in linear time. But i am wondering too, if this could be done with a probabilistic algorithm.