# Randomized 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 < 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.

• What is a binary pattern? What does it mean for P to occur in T? (I can think of some definitions but providing a reference will probably help.) – jmad May 7 '12 at 8:10
• KMP is good (and already mentioned). Boyer-Moore works even faster if properly implemented (see here). – rgrig May 7 '12 at 13:41
• The term you want to Wikipedia for is string searching (or matching). – Raphael May 10 '12 at 14:53

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

• But it runs in time $O(n+m)$ which is not equal to $O(n)$ if the pattern is not fixed! – Raphael May 10 '12 at 14:55
• @Raphael: The question says $m<n$. – rgrig May 10 '12 at 17:34
• @Raphael: Also, if $m>n$, you can just return FALSE immediately. – JeffE May 10 '12 at 19:47