Randomizd String Searching I need to detect whether a binary pattern P of length m occurs in a binary text T of length n where m

I want to state an algorithm that runs in time O(n) where we assume that arithmetic operations on O(log2n) 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−1n otherwise.

I think fingerprinting could help here. But I can't get it.
The average complexity of the search from the back to the front is equal to
$$
  \sum_{i=1}^n  \frac{2i}{n(n+1)}(n-i+1) = \frac{2}{n(n+1)}\sum_{i=1}^n i(n-i+1) = \frac{2}{n(n+1)} \frac{1}{6}n (n+1) (n+2) = \frac{1}{3}(n+2)
$$ 
which is indeed linear.