The Boyer–Moore Algorithm

Prerequisite: The Prefix Function and KMP Algorithm.

The KMP algorithm makes maximal use of prefix-matching information,

whereas the basic idea behind the BM algorithm is to obtain more information through suffix matching than through prefix matching, enabling faster character jumps.

Introduction

Imagine that our pattern string $pat$ is placed at the left end of the text string $string$, with their first characters aligned.

We make the following definitions and will not repeat them later:

The length of $pat$ is $patlen$. In particular, for a zero-indexed string, $patlastpos=patlen-1$ is defined as the position of the last character of $pat$;

the length of $string$ is $stringlen$, and $stringlastpos = stringlen-1$.

Suppose we know the $string$-th character $patlen$ of $char$ (aligned with the last character of $pat$). What information can we obtain?

Observation 1

If we know that the character $char$ does not occur in $pat$, we do not need to consider occurrences of $pat$ starting at the $string$st, $1$nd, ..., or $2$-th character of $patlen$; we can move $pat$ forward by $patlen$ characters at once.

Observation 2

More generally, if the rightmost occurrence of $pat$ in $char$ (that is, the position closest to the end) is $delta_1$ characters away from the end,

then we can move $pat$ backward by $delta_1$ characters without matching. If the shift distance were less than $delta_1$, the character $char$ alone could not be matched, so the pattern string $pat$ could not match either.

Therefore, unless $char$ can match the last character of $pat$, $string$ must skip $delta_1$ characters (equivalently, $pat$ moves backward by $delta_1$ characters). We can define a function $delta_1$ to calculate $delta_1(char)$:

Note that, obviously, this table only needs to be computed through position $patlastpos-1$.

Now suppose that $char$ matches the last character of $pat$. We then check whether the character before $char$ matches the second-to-last character of $pat$:

If it does, continue moving backward until the entire pattern $pat$ has been matched (we have then found a successful match of $string$ in $pat$);

alternatively, after matching the $pat$-th character from the end of $m$, we may encounter a mismatch at the $m+1$-th character from the end. We then want to move $pat$ forward to the next position where a match may be possible, and naturally we want to shift it as far as possible.

Observation 3(a)

In Observation 2, suppose that after matching the last $pat$ characters of $m$, a mismatch occurs at the $m+1$-th character from the end. To align the mismatching character in $string$ with the corresponding character in $pat$,

we need to shift $pat$ by $k$ characters, which means that we should focus on the $k+m$ characters afterward (the character in $pat$ aligned with the end of $string$ after shifting by k).

Since $k=delta_1-m$,

our attention should move $string$ characters forward along $delta_1-m+m = delta_1$.

However, we may be able to skip more characters. Continue reading.

Observation 3(b)

Suppose we know that the next $string$ characters of $m$ match the last $pat$ characters of $m$; call this substring $subpat$.

We also know that the substring after the mismatching character $string$ in $char$ matches $subpat$. If $pat$ occurs before the corresponding mismatching character in $subpat$, we can shift $pat$ by some distance

so that the $char$ occurring before the character corresponding to the mismatching $pat$ in $subpat$ (a plausible reoccurrence, abbreviated PR below) aligns with the $string$ in $subpat$. If $pat$ occurs multiple times in $subpat$, take the first one in the right-to-left suffix-matching order (the rightmost plausible reoccurrence, abbreviated RPR below).

Suppose $pat$ is shifted by $k$ characters (that is, the distance between the terminal $pat$ of $subpat$ and its rightmost plausible reoccurrence). Then our attention should move $string$ characters forward along $k+m$. We call this distance $delta_2(j)$:

Let $rpr(j)$ be the position of the rightmost plausible reoccurrence of $subpat=pat[j+1\dots patlastpos]$ when the mismatch occurs at $pat[j]$, with $rpr(j) < j$ (this is only a simple definition; the algorithm-design section below gives a more precise discussion). Then clearly $k=j-rpr(j),\ m=patlastpos-j$.

Therefore:

Thus, on a mismatch, we can skip $string$ characters of $\max(delta_1,delta_2)$.

Process

The arrow points to the mismatching character $char$:

$\mathtt{F}$ does not occur in $pat$. By Observation 1, move $pat$ forward by $patlen$ characters, namely 7 characters:

By Observation 2, we need to move $pat$ forward by 4 characters so that the hyphen aligns:

Now char:$\mathtt{T}$ matches. Move the pointer on $string$ one step to the left and continue matching:

By Observation 3(a), $\mathtt{L}$ mismatches. Since $\mathtt{L}$ does not occur in $pat$, move $pat$ by $k=delta_1-m=7-1=6$ characters, and move the pointer on $string$ forward by $delta_1=7$ characters:

Now $char$ again matches the last character $pat$ of $\mathtt{T}$. The pointer on $string$ moves left and matches $\mathtt{A}$; continuing left, it encounters a mismatch at $\mathtt{-}$:

Intuitively, by Observation 3(b), we now shift $pat$ by $k=5$ characters so that the suffix $\mathtt{AT}$ aligns. This shift gives the maximum movement of the $string$ pointer. Here $delta_2=k+patlastpos-j=5+6-4=7$, so the pointer on $string$ moves forward by 7 characters.

From the formal perspective, $delta_1=7-1-2=4,\ delta_2=7, \max(delta_1,delta_2)= 7$, which formally supports the jump from Observation 3(b):

We now find that every character in $pat$ equals the corresponding character in $string$; we have found a match of $string$ in $pat$. We used only 14 references to $string$: 7 comparisons were necessary to complete a successful match ($patlen=7$), and the other 7 let us skip 22 characters.

Algorithm Design

Initial Matching Algorithm

Explanation

Consider the following algorithm for string matching using $delta_1$ and $delta_2$:

If the algorithm above returns $\textbf{return}\ false$, $pat$ does not occur in $string$; if it returns a number, that number is the position of the first occurrence of $pat$ from the left in $string$.

Let us now describe more precisely how to calculate the function $delta_2$ on which $rpr(j)$ relies.

By the definition above, $rpr(j)$ is the position associated with a mismatch at $pat(j)$: it is the rightmost plausible reoccurrence position of the substring $subpat=pat[j+1\dots patlastpos]$ at $pat[j]$.

In other words, we need to find the best $k$ such that $pat[k\dots k+patlastpos-j-1]=pat[j+1\dots patlastpos]$, while also considering two special cases:

1. When $k<0$, this is equivalent to adding a virtual prefix before $pat$, and it is consistent with the principle of the $delta_2$ jump.
2. When $k>0$, if $pat[k-1]=pat[j]$, then $pat[k\dots k+patlastpos-j-1]$ cannot be a plausible reoccurrence of $subpat$.
   The reason is that $pat[j]$ is itself the mismatching character, so after shifting $pat$ by $k$ characters, suffix matching would still fail at $pat[k-1]$.

There are also two restrictions:

1. $k < j$. When $k=j$, we have $pat[k]=pat[j]$, so the character that mismatched at $pat[j]$ would also mismatch at $pat[k]$.
2. Since $delta_2(patlastpos)= 0$, define $rpr(patlastpos) = patlastpos$.

Process

Because understanding $rpr(j)$ is central to implementing the Boyer–Moore algorithm, we use the following two examples for a detailed explanation:

For $rpr(0)$, $subpat$ is $\mathtt{BCXXXABC}$. The rightmost plausible reoccurrence before $pat[0]$ can only be $\mathtt{[(BCXXX)ABC]XXXABC}$, so its position is -5, that is, $rpr(j)=-5$.

For $rpr(1)$, $subpat$ is $\mathtt{CXXXABC}$. The rightmost plausible reoccurrence before $pat[1]$ is $\mathtt{[(CXXX)ABC]XXXABC}$, so $rpr(j)=-4$.

For $rpr(2)$, $subpat$ is $\mathtt{XXXABC}$. The rightmost plausible reoccurrence before $pat[2]$ is $\mathtt{[(XXX)ABC]XXXABC}$, so $rpr(j)=-3$.

For $rpr(3)$, $subpat$ is $\mathtt{XXABC}$. The rightmost plausible reoccurrence before $pat[3]$ is $\mathtt{[(XX)ABC]XXXABC}$, so $rpr(j)=-2$.

For $rpr(4)$, $subpat$ is $\mathtt{XABC}$. The rightmost plausible reoccurrence before $pat[4]$ is $\mathtt{[(X)ABC]XXXABC}$, so $rpr(j)=-1$.

For $rpr(5)$, $subpat$ is $\mathtt{ABC}$. The rightmost plausible reoccurrence before $pat[5]$ is $\mathtt{[ABC]XXXABC}$, so $rpr(j)=0$.

For $rpr(6)$, $subpat$ is $\mathtt{BC}$. Since $string[0]=string[6]$, that is, $string[0]$ equals the mismatching character $string[6]$, $string[0\dots 2]$ is not a plausible reoccurrence of $subpat$. Thus the rightmost plausible reoccurrence is $\mathtt{[(BC)]ABCXXXABC}$, so $rpr(j)=-2$.

For $rpr(7)$, $subpat$ is $\mathtt{C}$. Similarly, since $string[7]=string[1]$, $string[1\dots 2]$ is not a plausible reoccurrence of $subpat$; the rightmost plausible reoccurrence is $\mathtt{[(C)]ABCXXXABC}$, so $rpr(j)=-1$.

For $rpr(8)$, by the definition of $delta_2$, $rpr(patlastpos)=patlastpos$, so $rpr(8)=8$.

Now consider another example:

For $rpr(0)$, $subpat$ is $\mathtt{BYXCDEYX}$. The rightmost plausible reoccurrence before $pat[0]$ can only be $\mathtt{[(BYXCDEYX)]ABYXCDEYX}$, so its position is -8, that is, $rpr(j)=-8$.

For $rpr(1)$, $subpat$ is $\mathtt{YXCDEYX}$. The only rightmost plausible reoccurrence before $pat[1]$ is $\mathtt{[(YXCDEYX)]ABYXCDEYX}$, so $rpr(j)=-7$.

For $rpr(2)$, $subpat$ is $\mathtt{XCDEYX}$. The only rightmost plausible reoccurrence before $pat[2]$ is $\mathtt{[(XCDEYX)]ABYXCDEYX}$, so $rpr(j)=-6$.

For $rpr(3)$, $subpat$ is $\mathtt{CDEYX}$. The only rightmost plausible reoccurrence before $pat[3]$ is $\mathtt{[(CDEYX)]ABYXCDEYX}$, so $rpr(j)=-5$.

For $rpr(4)$, $subpat$ is $\mathtt{DEYX}$. The only rightmost plausible reoccurrence before $pat[4]$ is $\mathtt{[(DEYX)]ABYXCDEYX}$, so $rpr(j)=-4$.

For $rpr(5)$, $subpat$ is $\mathtt{EYX}$. The only rightmost plausible reoccurrence before $pat[5]$ is $\mathtt{[(EYX)]ABYXCDEYX}$, so $rpr(j)=-3$.

For $rpr(6)$, $subpat$ is $\mathtt{YX}$. Since $string[2\dots 3]=string[7\dots 8]$ and $string[6]\neq string[1]$, the rightmost plausible reoccurrence before $pat[6]$ is $\mathtt{AB[YX]CDEYX}$, so $rpr(j)=2$.

For $rpr(7)$, $subpat$ is $\mathtt{X}$. Although $string[3]=string[8]$, $string[2] = string[7]$, so the rightmost plausible reoccurrence before $pat[7]$ is $\mathtt{[X]ABYXCDEYX}$, so $rpr(j)=-1$;

For $rpr(8)$, by the definition of $delta_2$, $rpr(patlastpos)=patlastpos$, so $rpr(8)=8$.

An Improvement to the Matching Algorithm

Finally, in practice, about 80% of the search time is estimated to be spent on the jump in Observation 1: $string[i]$ does not match $pat[patlastpos]$, so we jump the entire $patlen$ and begin the next match.

This can be specially optimized:

Define $delta0$:

Replacing $delta0$ with $delta_1$ gives the improved matching algorithm:

Here, $large$ has multiple roles: it performs fast bad-character jumps similar to the Horspool algorithm introduced later, and it helps detect when the string search is complete.

Compared with the original algorithm, this improvement avoids the unnecessary computation of $delta_2$ on every Observation 1 jump, giving a clear performance improvement for searching in usual alphabets.

Details of Building delta2

Introduction

In the Boyer and Moor paper¹ on the Boyer–Moore algorithm in the October 1977 issue of Communications of the ACM, only the static $delta_2$ table was described,

whereas the discussion of the concrete construction of $delta_2$ appeared in the paper² on the KMP algorithm jointly published by Knuth, Morris, and Pratt in the June 1977 issue of SIAM Journal on Computing.

Naive Algorithm

Before introducing Knuth's construction algorithm for $delta_2$, the definition gives a naive algorithm suitable for small problems:

1. For every position [0, patlen) in the interval i, determine the range of possible reoccurrence positions from the length of subpat, namely [-subpatlen, i].
2. Compare possible reoccurrence positions character by character from right to left, looking for the rightmost reoccurrence of $delta_2$ satisfying the requirements of $subpat$.
3. Finally, remember to set $delta_2(lastpos)= 0$.

use std::cmp::PartialEq;

pub fn build_delta_2_table_naive(p: &[impl PartialEq]) -> Vec<usize> {
    let patlen = p.len();
    let lastpos = patlen - 1;
    let mut delta_2 = vec![];

    for i in 0..patlen {
        let subpatlen = (lastpos - i) as isize;

        if subpatlen == 0 {
            delta_2.push(0);
            break;
        }

        for j in (-subpatlen..(i + 1) as isize).rev() {
            // Match subpat
            if (j..j + subpatlen)
            .zip(i + 1..patlen)
            .all(|(rpr_index, subpat_index)| {
                if rpr_index < 0 {
                    return true;
                }

                if p[rpr_index as usize] == p[subpat_index] {
                    return true;
                }

                false
            })
            && (j <= 0 || p[(j - 1) as usize] != p[i])
            {
                delta_2.push((lastpos as isize - j) as usize);
                break;
            }
        }
    }

    delta_2
}

In particular, the following explanations of relevant Rust language features are necessary and will not be repeated:

• usize and isize are unsigned and signed integers with the same number of bytes as a memory pointer. On a 32-bit machine they correspond to u32 and i32, and on a 64-bit machine to u64 and i64.
• Indices into arrays, vectors, and slices use numbers of type usize (because they perform random memory access and indices cannot be negative). Therefore, handling negative values requires isize; indexing then requires usize, which is why the as keyword is used for an explicit conversion between the two.
• impl PartialEq is used only as a generic parameter, so it supports both Unicode values encoded in char and binary u8 values.

Obviously, the time complexity of this brute-force algorithm is $O(n^3)$.

Efficient Algorithm

Next we introduce an efficient algorithm with time complexity $O(n)$ and an additional space complexity of $O(n)$.

Although Knuth proposed this construction in 1977, his original construction algorithm has a flaw: for some $pat$, it cannot produce a $delta_2$ satisfying the definition.

Rytter proposed a correction in a 1980 article³ in SIAM Journal on Computing. The following is the construction algorithm for $delta_2$:

Since the definition of $delta_2$ is complicated, first classify cases by the reoccurrence position of $subpat$ and handle each class separately. This is the key idea for an efficient implementation.

Classify them from farthest to nearest, that is, from larger to smaller offsets:

1. The entire reoccurrence of $subpat$ is completely to the left of $pat$, for example $\mathtt{[(EYX)]ABYXCDEYX}$. In this case, $delta_2(j) = patlastpos\times 2 - j$.

2. Part of the reoccurrence of $subpat$ is to the left of $pat$, while the rest is at the head of $pat$, for example $\mathtt{[(XX)ABC]XXXABC}$. In this case, $patlastpos < delta_2(j) < patlastpos\times 2 - j$.
   The boundary case where the entire $subpat$ is at the head of $pat$ is also placed here (though it may be classified below in an implementation), for example $\mathtt{[ABC]XXXABC}$, where $patlastpos = delta_2(j)$.

3. The reoccurrence of $subpat$ is entirely inside $pat$, for example $\mathtt{AB[YX]CDEYX}$. In this case, $delta_2(j) < patlastpos$.

Now let us discuss how to compute these three cases efficiently:

First Case

This is the simplest case; it only needs one traversal and can also initialize $delta_2$ along the way.

Second Case

When does a reoccurrence of $subpat$ have one part to the left of $pat$ and one part at the head of $pat$? It occurs when a suffix of $subpat$ equals a prefix of $pat$,

as in the earlier example:

$delta_2(3)$ has the reoccurrence $\mathtt{[(XX)ABC]XXXABC}$; the suffix of $subpat$ $\mathtt{XXABC}$ and the prefix of pat share the equal part $\mathtt{ABC}$.

In fact, computing both the second and third cases relies on computing and applying the prefix function.

As long as $j$ is chosen so that $subpat$ contains this equal suffix, we obtain the reoccurrence of $subpat$ in the second case. In the example, we only need $j \leqslant 5$,

and $j = 5$ is the boundary case in which $subpat$ is entirely at the head of $pat$.

We can calculate $delta_2(j)$ in this case:

Let the length of this equal prefix and suffix be $\textit{prefixlen}$. Since $subpatlen = patlastpos - j$, the length of the part to the left of $pat$ is $subpatlen-\textit{prefixlen}$,

and $rpr(j) = -(subpatlen-\textit{prefixlen})$, so $delta_2(j) = patlastpos - rpr(j) = patlastpos \times 2 - j - \textit{prefixlen}$.

There may be multiple pairs of equal prefixes and suffixes afterward, for example:

For $j\leq2$, there is $\mathtt{ABAABAA}$; for $2< j \leq 5$, there is $\mathtt{ABAA}$; and for $5<j\leq8$, there is $\mathtt{A}$.

The flaw in Knuth's algorithm is that it considers only the longest pair. In fact, we must consider every case in which a suffix of $subpat$ equals a prefix of $pat$, which is equivalent to computing all equal proper suffixes and proper prefixes of $pat$, and partitioning the range of $j$ to calculate different $delta_2(j)$ values by decreasing length.

Using the prefix function and the transition equation in reverse, $j^{(n)} = \pi[j^{(n-1)}-1]$, obtain all lengths of equal proper prefixes and proper suffixes of $pat$. Starting from $\pi[patlastpos]$, the length of the longest pair, repeatedly run the transition equation backward to obtain the next shorter equal proper prefix and suffix.

This completes the computation of $delta_2$ for the second case.

Third Case

The reoccurrence of $subpat$ lies exactly inside $pat$ (not including the head of $pat$); that is, search for $pat[0\dots patlastpos-1]$ in $subpat$ from right to left.

If we solve this with the BM algorithm, we obtain a recursive implementation of the third BM case, with the base condition $patlen \leqslant 2$.

Moreover, by the definition of $delta_2$, the character immediately before the found reoccurrence of $subpat$ (the one to its left) must differ from the character immediately before $pat$ as a suffix of $subpat$.

This suggests using a process similar to prefix-function computation, but with left and right reversed:

• Two pointers point to the left endpoint of the substring and the “prefix” position of the longest common prefix and suffix of the substring. Move them from right to left, continuing when the two pointed-to characters are equal; this corresponds to extending the “prefix”.
• When the characters differ, the part that was equal satisfies the reoccurrence requirement of $delta_2$, and move the pointer to the “prefix” position backward until a new pair of equal characters is formed or the boundary is crossed.

As with the prefix function, an auxiliary array is needed for fallback. The space of the prefix array generated while computing the second case can be reused.

Implementation

use std::cmp::PartialEq;
use std::cmp::min;

pub fn build_delta_2_table_improved_minghu6(p: &[impl PartialEq]) -> Vec<usize> {
    let patlen = p.len();
    let lastpos = patlen - 1;
    let mut delta_2 = Vec::with_capacity(patlen);

    // First case
    // delta_2[j] = lastpos * 2 - j
    for i in 0..patlen {
        delta_2.push(lastpos * 2 - i);
    }

    // Second case
    // lastpos <= delata2[j] = lastpos * 2 - j
    let pi = compute_pi(p);  // Compute the prefix function
    let mut i = lastpos;
    let mut last_i = lastpos; // Only for initialization
    while pi[i] > 0 {
        let start;
        let end;

        if i == lastpos {
            start = 0;
        } else {
            start = patlen - pi[last_i];
        }

        end = patlen - pi[i];

        for j in start..end {
            delta_2[j] = lastpos * 2 - j - pi[i];
        }

        last_i = i;
        i = pi[i] - 1;
    }

    // Third case
    // delata2[j] < lastpos
    let mut j = lastpos;
    let mut t = patlen;
    let mut f = pi;
    loop {
        f[j] = t;
        while t < patlen && p[j] != p[t] {
            // Use min to ensure that later fallbacks do not overwrite earlier data
            delta_2[t] = min(delta_2[t], lastpos - 1 - j);
            t = f[t];
        }

        t -= 1;
        if j == 0 {
            break;
        }
        j -= 1;
    }

    // Has no practical meaning; it is included for a complete definition
    delta_2[lastpos] = 0;

    delta_2
}

Improving the Worst Case for Multiple Matches with the Galil Rule

Multiple Matches in Suffix-Matching Algorithms

The search algorithm above only considers finding the first match of $string$ in $pat$. Finding all matches of $string$ in $pat$ involves many different algorithmic ideas; the central question is how to use information from previously successful matches to reduce the worst-case time complexity to linear.

After an original successful match, simply moving the pointer in $string$ forward by $patlen$ and restarting suffix matching can bring the worst-case time complexity back to $O(mn)$ (by convention, $m$ is $patlen$ and $n$ is $stringlen$ below).

For example, consider the extreme case $pat$: $\mathtt{AAA}$ and $string$: $\mathtt{AAAAA}\dots$.

One method proposed by Knuth records the $patlen$-length characters in a set of “finite” states. This algorithm guarantees that each character in $string$ is compared at most once, but the finite state set may be quite large: for a $pat$ whose characters are pairwise distinct, it needs $\dfrac{1}{2}m^{2}+m$ states.

Next we introduce the Galil algorithm⁴, whose idea is simple and requires no additional preprocessing overhead.

Galil Rule

Suppose $pat$ is a prefix of a string formed by repeating some substring $U$ n times, $UUUU\dots$. We call $U$ a period of $pat$.

For example, $pat: \mathtt{ABCABCAB}$ is a prefix of the repetition of $\mathtt{ABC}$ represented by $\mathtt{ABCABCABC}$, so the period length of $\mathtt{ABC}$ is $3$ for $pat$; equivalently, $pat$ satisfies $pat[i] = pat[i+3]$.

$pat$ has at least one period whose length equals its own length. Let the shortest period be $k$, with $k\leq patlen$.

During the search, suppose $pat$ has successfully matched once. By the properties of the period, we only need to move $string$ forward by $k$ characters and compare whether these $k$ characters correspond, which directly determines whether another match of $pat$ exists.

To compute the length of this shortest period, suppose we know an equal prefix and suffix of $pat$, both of length $\textit{prefixlen}$. Then $pat[i] = pat[i+(patlen-\textit{prefixlen})]$, giving a period of length $patlen-\textit{prefixlen}$.

When we know the longest equal prefix and suffix of $pat$, we obtain the shortest period of $pat$.

The length of the longest equal prefix and suffix, $\pi[patlastpos]$, is already available from the computation of $delta_2$. Therefore, no additional preprocessing time or space is needed to improve the worst-case time complexity of the suffix-matching algorithm to linear.

#[cfg(target_pointer_width = "64")]
const LARGE: usize = 10_000_000_000_000_000_000;

#[cfg(not(target_pointer_width = "64"))]
const LARGE: usize = 2_000_000_000;

pub struct BMPattern<'a> {
    pat_bytes: &'a [u8],
    delta_1: [usize; 256],
    delta_2: Vec<usize>,
    k: usize  // The shortest period length of pat
}

impl<'a> BMPattern<'a> {
    // ...

    pub fn find_all(&self, string: &str) -> Vec<usize> {
        let mut result = vec![];
        let string_bytes = string.as_bytes();
        let stringlen = string_bytes.len();
        let patlen = self.pat_bytes.len();
        let pat_last_pos = patlen - 1;
        let mut string_index = pat_last_pos;
        let mut pat_index;
        let l0 =  patlen - self.k;
        let mut l = 0;

        while string_index < stringlen {
            let old_string_index = string_index;

            while string_index < stringlen {
                string_index += self.delta0(string_bytes[string_index]);
            }
            if string_index < LARGE {
                break;
            }

            string_index -= LARGE;

            // If string_index moved, at least one failed match has occurred since the last successful match.
            // The offset for the Galil rule's second match must be reset to zero.
            if old_string_index < string_index {
                l = 0;
            }

            pat_index = pat_last_pos;

            while pat_index > l && string_bytes[string_index] == self.pat_bytes[pat_index] {
                string_index -= 1;
                pat_index -= 1;
            }

            if pat_index == l && string_bytes[string_index] == self.pat_bytes[pat_index] {
                result.push(string_index - l);

                string_index += pat_last_pos - l + self.k;
                l = l0;
            } else {
                l = 0;
                string_index += max(
                    self.delta_1[string_bytes[string_index] as usize],
                    self.delta_2[pat_index],
                );
            }
        }

        result
    }
}

Practical Performance Impact of the Worst Case

From a practical perspective, the theoretical worst case does not easily affect performance. Even on random text over a very small alphabet of only 4 characters, its impact is difficult to observe.

Consequently, without careful design, using the Galil rule can slightly hurt average performance. For certain extreme $pat$ and $string$ pairs, such as the example $pat$: $\mathtt{AAA}$ and $string$: $\mathtt{AAAAA}\dots$, however, applying the Galil rule does improve performance several-fold.

Improved Algorithms

Simplified Boyer–Moore Algorithm

The most complicated part of the BM algorithm is building the $delta_2$ table (the good-suffix table). In practice, matching performance on ordinary alphabets mainly depends on the $delta_1$ table (the bad-character table), so a simplified BM algorithm that uses only the $delta_1$ table has emerged; its performance is usually only slightly different from the original.

Boyer–Moore–Horspool Algorithm

The Horspool algorithm also uses the bad-character rule, applying $pat$ to the character aligned with the end of $delta_1$. It is similar to the improvement of the original matching algorithm and usually performs better than the original version.

pub struct HorspoolPattern<'a> {
    pat_bytes: &'a [u8],
    bm_bc: [usize; 256],
}

impl<'a> HorspoolPattern<'a> {
    // ...
    pub fn find_all(&self, string: &str) -> Vec<usize> {
        let mut result = vec![];
        let string_bytes = string.as_bytes();
        let stringlen = string_bytes.len();
        let pat_last_pos = self.pat_bytes.len() - 1;
        let mut string_index = pat_last_pos;

        while string_index < stringlen {
            if &string_bytes[string_index-pat_last_pos..string_index+1] == self.pat_bytes {
                result.push(string_index-pat_last_pos);
            }

            string_index += self.bm_bc[string_bytes[string_index] as usize];
        }

        result
    }
}

Boyer–Moore–Sunday Algorithm

The Sunday algorithm also uses the bad-character rule, but compared with Horspool it goes one step further and directly considers the character after the one aligned with the end of $pat$.

Implementing it only requires a slight modification to the $delta_1$ table, equivalent to building it for a $patlen+1$ of length $pat$.

The Sunday algorithm is often used as one of the simplest practical algorithms with the best average performance in general cases. It is usually a little faster than Horspool and BM.

pub struct SundayPattern<'a> {
    pat_bytes: &'a [u8],
    sunday_bc: [usize; 256],
}

impl<'a> SundayPattern<'a> {
    // ...
    fn build_sunday_bc(p: &'a [u8]) -> [usize; 256] {
        let mut sunday_bc_table = [p.len() + 1; 256];

        for i in 0..p.len() {
            sunday_bc_table[p[i] as usize] = p.len() - i;
        }

        sunday_bc_table
    }

    pub fn find_all(&self, string: &str) -> Vec<usize> {
        let mut result = vec![];
        let string_bytes = string.as_bytes();
        let pat_last_pos = self.pat_bytes.len() - 1;
        let stringlen = string_bytes.len();
        let mut string_index = pat_last_pos;

        while string_index < stringlen {
            if &string_bytes[string_index - pat_last_pos..string_index+1] == self.pat_bytes {
                result.push(string_index - pat_last_pos);
            }

            if string_index + 1 == stringlen {
                break;
            }

            string_index += self.sunday_bc[string_bytes[string_index + 1] as usize];
        }

        result
    }
}