0
$\begingroup$

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)?

Are there any sublinear expected-time string matching algorithms (on all alphabet sizes)?

$\endgroup$
  • 5
    $\begingroup$ Please do not use cstheory for self-advertisement. $\endgroup$ – Kaveh Sep 8 '14 at 13:57
  • 6
    $\begingroup$ What do you mean by "Boyer-Moore"? en.wikipedia.org/wiki/… describes two algorithms, one of which is linear and the other of which can be nonlinear. The Goodrich–Tamassia text Algorithm Design presents a third, "simplified" version of the algorithm which is also nonlinear. $\endgroup$ – David Eppstein Sep 8 '14 at 20:35
  • $\begingroup$ Kaveh changed my post rather drastically, but what I mean is that the standard Boyer-Moore algorithms appear to be linear on average for small alphabets. I had posted a true expected-time sublinear algorithm, for all alphabets, but it was removed. Should I try again? $\endgroup$ – daniel pehoushek Sep 9 '14 at 11:55
  • 2
    $\begingroup$ I removed the part where you advertised your obscure algorithm and kept the question. Discussion about your algorithm was not needed for the question. If you want to add that back then you don't really have a question but just want to self-advertise which is not welcome here. $\endgroup$ – Kaveh Sep 9 '14 at 12:58
  • $\begingroup$ I thought theoreticians would be interested in a true sublinear string matching algorithm. You replaced that with a "does such exist" question. I would also be interested in a proof that my algorithm is optimal, on random strings and all alphabets. Maybe I could pose the optimality question, where the answer would be a proof? Also, the fact that Boyer-Moore is linear on small alphabets means there are no other sublinear string matching algorithms, that I know of, on all alphabets. $\endgroup$ – daniel pehoushek Sep 10 '14 at 16:25
-3
$\begingroup$

Here is a true sublinear string matching algorithm, on all alphabet sizes, which answers the question Kaveh posted. My question was: Is Boyer-Moore actually linear on small alphabets?

The log base below is $|\Sigma|$, and (ceiling of) $logM$ (often just one) is implied.

Preprocess the Pattern into a lookup table, with $M-logM+1$ keys, each key having size $logM$, and with associated key positions in the Pattern. Converting sequences of $logM$ letters into array indices is the only tricky part. The table size is $|\Sigma|$ raised to ceiling of $logM$, for easy indexing. Each bucket is a short, possibly empty, list of key positions. Run time: $O( MlogM )$.

Main: Skip through Text positions $k$ by $(M - logM + 1)$, constructing a $logM$ sized search key at Text positions $k$ thru $k + logM -1$. Look up the search key in the table. If found, naively attempt to match the Pattern at Text[$k$ - key position]. The naive attempt almost certainly fails in $logM$ comparisons. The only tricky part is that a key may occur in multiple Pattern positions. The expected number of test positions is $O(1)$. Expected run time: $O( (N/M)logM )$.

Post: Garbage collect the preprocessing space, $O(MlogM)$.

A proof that Main is optimal for $N>M^2$, on all alphabet sizes, is needed.

$\endgroup$

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.