Randomized String Searching

Question

I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m < n$.

I want to state an algorithm that runs in time $O(n)$ where we assume that arithmetic operations on $O(\log_2 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 of at least $1 - \frac{1}{n}$ otherwise.

I think fingerprinting could help here. But I can't get it.

Answer 1

The Knuth-Morris-Pratt algorithm does this in linear time without any error.