3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – jmad May 7 '12 at 8:10
  • $\begingroup$ KMP is good (and already mentioned). Boyer-Moore works even faster if properly implemented (see here). $\endgroup$ – rgrig May 7 '12 at 13:41
  • $\begingroup$ The term you want to Wikipedia for is string searching (or matching). $\endgroup$ – Raphael May 10 '12 at 14:53
9
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.