<p>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?</p>

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

<p>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 )$.</p>

<p>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 )$.</p>

<p>Post: Garbage collect the preprocessing space, $O(MlogM)$.</p>

<p>A proof that Main is optimal for $N&gt;M^2$, on all alphabet sizes, is needed.</p>

CC BY-SA 3.0
2014-09-16T10:20:19.813Z
2014-09-16T10:20:19.813Z
daniel pehoushek
<p>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|$)?  </p>

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

CC BY-SA 3.0
2014-09-08T13:57:49.613Z
Please do not use cstheory for self-advertisement.
Kaveh
CC BY-SA 3.0
2014-09-08T20:35:18.557Z
What do you mean by "Boyer-Moore"? https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm 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.
David Eppstein
CC BY-SA 3.0
2014-09-09T11:55:08.433Z
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?
daniel pehoushek
CC BY-SA 3.0
2014-09-09T12:58:21.123Z
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.
Kaveh
CC BY-SA 3.0
2014-09-10T16:25:44.657Z
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.
daniel pehoushek
<ds.algorithms><ds.data-structures><time-complexity><string-matching><string-search>
Is the running time of Boyer-Moore linear?
daniel pehoushek
# Is the running time of Boyer-Moore linear?

(Asked by: username_0 on 2014-09-08)

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)?

**Tags:** ds.algorithms, ds.data-structures, time-complexity, string-matching, string-search

> **Comments:**
> **username_1**: Please do not use cstheory for self-advertisement.  
> **username_2**: What do you mean by "Boyer-Moore"? https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm 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.  
> **username_0**: username_1 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?  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_0 on 2014-09-16. Score: -3

Here is a true sublinear string matching algorithm, on all alphabet sizes, which answers the question username_1 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.


---

