Boyer-Moore Algorithm

Example with paper in the lecture slides:

The gist is to start with the last letter of the pattern $P$ and try to match with $T$. If, the letter we are matching does not appear in $P$ at all, we shift pass the letter, if we found a letter that doesn’t match, we align the guess until the letter in $P$ aligns with the letter in $T$. If the letter appears twice in our $P$, we shift the guess to align with the second occurrence in $P$.

Note

Worst-case runtime to execute the Boyer-Moore algorithm, with only the bad character heuristic is $\Theta (nm+|\sum |)$.

Question: Is the best case when c is not found because we get to skip over the segment of length m? And is the worst case when $L[c]>j$, for $\Theta (m)$, because we have to shift by 1 unit each time, where is the length of the string? Answer: For the best case, yes, it is because we move length of . With the worst, it may be a case that where we can only shift our guess by index of 1.

When $L(c)<j$ Remember: $i=i+(m-1)-L(c)$

If $L(c)>j$, we use brute force step:

Pseudocode:

Example of Boyer-More:

Questions

1. For the pattern $P=patakaa$, in the last-occurrence function $L$, we have:

• $L(a)=6$

2. Given a pattern $P$ of length $m$ and text $T$ of length $n$, the worst-case runtime to execute the Boyer-Moore algorithm, with only the bad character heuristic is $\Theta (nm+|\sum |)$?

• True. But why??? I thought it was $\Theta (nm)$. So the sum is to account for running over occurrence array. $\to$ $|\sum |$ is there to account run-time to compute last occurrence array. $nm$ is there as we may check all characters in sub-text and only can shift our guess by index of 1 (or something similar).!

3. In the Boyer-Moore algorithm, its possible to shift pattern ahead $m$ characters with a single check.

• False, in the bad character heuristic, when mismatch occurs, it allows to shift the pattern to the rightmost occurrence of the mismatched character in the pattern is aligned with the mismatched character in the text. So it is less than $m$.

4. Suppose you are given a text $T$ of length $n$ and a pattern $P$ of length $\log n$. What is the pre-processing time of the Boyer-Moore algorithm?

• To apply the bad character heuristic, we need to create a “bad character” table that records the rightmost occurrence of each character in the pattern. This preprocessing step takes $O(m+|\Sigma |)$ time, where m is the length of the pattern P, and |Σ| is the size of the alphabet (the number of unique characters). In the worst case, |Σ| is a constant factor, so the bad character heuristic preprocessing takes O(m) time. In this case, it would be $O(\log n+|\sum |)$.

5. Assume you are given a pattern of length $m$ and text of length $n$ and that any pre-processing steps have been completed. The best-case runtime of the Boyer-Moore algorithm when the pattern is not found in the text is:

• $\Theta (n/m)$, but why??