Boyer-Moore String-Search Algorithm

The Boyer-Moore string-search algorithm is a foundational pattern-matching procedure in computation and algorithms that locates occurrences of a pattern string P[1..m] inside a text string T[1..n] by scanning the characters of the pattern from right to left (j = m down to 1) at each candidate alignment shift s while advancing the window across the text from left to right. Invented by Robert S. Boyer and J Strother Moore at SRI International and Xerox Palo Alto Research Center and published in Communications of the ACM in October 1977, the algorithm introduced a counterintuitive insight: by testing the rightmost character of the pattern P[m] against the text character T[s + m] first, a single mismatch on a character that does not appear anywhere in P directly proves that none of the m overlapping alignments spanning T[s + m] can match, allowing the matcher to leap forward by m text positions in a single step.

Unlike the Knuth-Morris-Pratt algorithm, which inspects every text symbol at least once and performs Θ(n) operations in both the best and worst cases, the Boyer-Moore algorithm runs in sublinear O(n / m) average time on natural-language text, source code, and protein sequences, typically inspecting only 20% to 30% of the bytes in the input file. Combined with Zvi Galil's 1979 prefix-memorization rule, it simultaneously achieves linear Θ(n + m) worst-case time in computational complexity theory, making Boyer-Moore and its streamlined descendants (Boyer-Moore-Horspool and Sunday Quick Search) the standard engines inside utilities such as UNIX/GNU grep and modern standard-library substring search routines.

Window Alignment and Maximum Shift Selection

At any stage of the search, the pattern P[1..m] is aligned at shift offset s ∈ {0, 1, ..., n − m} against the text window T[s + 1 .. s + m]. The matcher compares P[j] against T[s + j] starting from the rightmost pattern index j = m and decrementing j down toward 1:

• If P[j] = T[s + j] for all j = m, m − 1, ..., 1, a full match is reported at shift s.
• Otherwise, suppose the first mismatch from the right occurs at pattern index j (1 ≤ j ≤ m), meaning the suffix t = P[j + 1 .. m] of length m − j has already matched T[s + j + 1 .. s + m], while P[j] ≠ T[s + j].

At this mismatch, the algorithm consults two precomputed tables—the bad-character rule (Δ_bc) and the strong good-suffix rule (Δ_gs)—and advances the alignment shift s by the larger of the two safe displacements:

s ← s + max(Δ_bc(j, T[s + j]), Δ_gs(j))

1. The Bad-Character Shift Rule (Δ_bc)

Let c = T[s + j] ∈ Σ be the text character that caused the mismatch against P[j]. The bad-character rule uses the precomputed rightmost-occurrence table R : Σ → {0, 1, ..., m}, defined as:

• R(c) = max { k : 1 ≤ k ≤ m and P[k] = c } if c occurs in P, and R(c) = 0 if c does not occur in P.

When P[j] ≠ c, the pattern cannot match at any shift finer than aligning an occurrence of c inside P with T[s + j]:

• Case 1 (c does not occur in P, so R(c) = 0): No alignment of P overlapping position s + j can succeed. The pattern shifts right past s + j, giving Δ_bc = j. When the mismatch happens on the very first comparison at the right end of the window (j = m), the pattern jumps forward by the full pattern length Δ_bc = m.
• Case 2 (R(c) < j): The rightmost occurrence of c in P lies to the left of j, so shifting P right by Δ_bc = j − R(c) aligns P[R(c)] with T[s + j].
• Case 3 (R(c) > j): The rightmost occurrence of c in P lies to the right of j (inside the already-matched suffix). Shifting P to align P[R(c)] with T[s + j] would move the window backward (j − R(c) < 0). In the standard single-entry table, the bad-character rule falls back to a minimal forward step Δ_bc = max(1, j − R(c)) = 1 (and defers to the good-suffix rule), whereas the extended bad-character rule stores a list of occurrences of c in P to locate the rightmost index k < j with P[k] = c.

2. The Strong Good-Suffix Shift Rule (Δ_gs)

When the mismatch occurs at index j < m, the matcher has already verified that the non-empty suffix t = P[j + 1 .. m] matches the text substring T[s + j + 1 .. s + m]. The strong good-suffix rule exploits this matched block t via two subcases:

• Subcase 2a (Internal Re-Occurrence with Distinct Preceding Character): Find the rightmost substring P[k − (m − j) + 1 .. k] inside P (with k < m) that equals the matched suffix t = P[j + 1 .. m] and is preceded by a character P[k − (m − j)] ≠ P[j]. Requiring P[k − (m − j)] ≠ P[j] (the strong condition introduced by Knuth, Morris, and Pratt in 1977) prevents shifting a second copy of the identical mismatching character P[j] onto T[s + j]. If such a k exists, Δ_gs(j) = m − k.
• Subcase 2b (Longest Prefix Border Fallback): If no internal occurrence of t satisfies Subcase 2a, the pattern cannot fully overlap t again. However, a prefix of P may still match a suffix of t. Let l < m − j be the length of the longest prefix P[1..l] that equals the suffix P[m − l + 1 .. m] of t. Then the window shifts by Δ_gs(j) = m − l (or by Δ_gs(j) = m if l = 0).

Both good-suffix subcases are precomputed in Θ(m) time and space before scanning T by running the Knuth-Morris-Pratt algorithm prefix computation on the reversed pattern P^R (or via Gusfield's Z-array Z[i], which records the length of the longest substring starting at i that matches a suffix of P).

Suppose we search for the 7-character pattern P[1..7] = "GCAGAGAG" (m = 8: P = "GCAGAGAG") inside the 24-character DNA sequence T = "GCATCGCAGAGAGTATACAGTACG" (n = 24):

Notice what happens at Step 2 (s = 1): after matching P[8] = 'G' and failing at j = 7 against T[8] = 'C', the bad-character rule shifts s by +5 to s = 6 (where P = "GCAGAGAG" occurs at s = 5 in T[6..13] = "GCAGAGAG" if Step 1 had shifted to s = 5 via good-suffix). And at Step 3 (s = 6), encountering the character 'T' (which does not appear anywhere in "GCAGAGAG", so R('T') = 0) at j = 8 allows the matcher to leap 8 characters forward in a single comparison, skipping over 7 intermediate text characters without ever reading them.

Periodic Pathologies and Galil's Linear-Time Rule

When the pattern P does not appear in T (or appears only in non-overlapping regions), Guibas and Odlyzko (1980) and Richard Cole (1994) proved that the standard Boyer-Moore algorithm with the strong good-suffix rule performs at most 3n character comparisons in the worst case—even on strongly periodic inputs.

However, if a periodic pattern P = "AAAAA" (m = 5) occurs at every position inside T = "AAAAAAAAAA..." (n characters of 'A'), each complete match of length m shifts the window by only Δ_gs(0) = 1 position, causing the unmodified algorithm to re-compare all m characters at every shift in Θ(nm) time. In 1979, Zvi Galil resolved this pathology with Galil's rule: whenever a shift of size d < m is dictated by Subcase 2b (meaning the prefix P[1..m − d] is already known to match the text suffix from the previous window), the matcher remembers the boundary index m − d and stops its right-to-left scan at j = m − d + 1 on the next step rather than re-testing characters 1..m − d. With Galil's rule, Boyer-Moore runs in worst-case Θ(n + m) time across all inputs, matching the worst-case bound of Knuth-Morris-Pratt while preserving O(n / m) sublinear average speed.

Boyer-Moore-Horspool (1980) and Sunday Quick Search (1990)

On alphabets of size |Σ| ≥ 16 (such as 256-byte ASCII/UTF-8 text or 20-letter amino-acid sequences in bioinformatics), mismatches occur almost always near the rightmost position j = m, where the bad-character shift dominates the good-suffix shift. Because maintaining and branching on the good-suffix table adds instruction overhead in tight CPU loops, two simplified variants are widely used in practice:

1. Boyer-Moore-Horspool (BMH, 1980): Proposed by R. Nigel Horspool, BMH drops the good-suffix table and computes the bad-character shift always using the rightmost character of the current text window, T[s + m] (regardless of which internal position j ≤ m failed), with shift table D[c] = m − R_1..m−1(c). This ensures D[c] ≥ 1 on every step with a single 256-entry lookup table.
2. Sunday's Quick Search (1990): Proposed by Daniel M. Sunday, Quick Search keys the shift table on the character one position to the right of the current window, T[s + m + 1], which must participate in any subsequent alignment shift s′ > s, increasing the maximum single-step jump from m to m + 1.

Why is the Boyer-Moore algorithm faster when the pattern is longer?

When the first comparison at the right end of the window (j = m) encounters a character c = T[s + m] that does not appear in P, the bad-character rule advances the window by m positions at the cost of 1 comparison (1 / m comparisons per text character). As m grows (provided m stays smaller than the alphabet size |Σ|), each mismatch skips across a wider span of text, reducing the total number of character inspections until the probability 1 − (1 − 1/|Σ|)^m that c occurs inside P approaches 1.

Why is the "strong" condition required in the good-suffix rule?

In Boyer and Moore's original 1977 formulation, the weak good-suffix table shifted the matched suffix t = P[j + 1 .. m] to its rightmost earlier copy in P even if that copy was preceded by the same mismatching character P[j]. That weak shift causes a repeat mismatch on T[s + j] and allows worst-case inputs to force Θ(nm) comparisons; requiring the preceding character to differ (P[k − (m − j)] ≠ P[j]) eliminates repeat mismatches and establishes the 3n comparison bound.

How does Boyer-Moore compare with FM-index / Burrows-Wheeler search in genomics?

Boyer-Moore preprocesses the pattern P in Θ(m) time and scans an unindexed text T in O(n / m) time, making it ideal for one-off searches over streaming or unindexed FASTA files. By contrast, an FM-index built on the Burrows–Wheeler transform preprocesses the reference text T once in Θ(n) time so that millions of sequencing reads of length m can be aligned in O(m) time per read without scanning T.

1. Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762–772. https://doi.org/10.1145/359842.359859
2. Galil, Z. (1979). On improving the worst case running time of the Boyer-Moore string matching algorithm. Communications of the ACM, 22(9), 505–508. https://doi.org/10.1145/359146.359148
3. Horspool, R. N. (1980). Practical fast searching in strings. Software: Practice and Experience, 10(6), 501–506. https://doi.org/10.1002/spe.4380100608
4. Cole, R. (1994). Tight bounds on the complexity of the Boyer-Moore string matching algorithm. SIAM Journal on Computing, 23(5), 1075–1091. https://doi.org/10.1137/S0097539791195543
5. Sunday, D. M. (1990). A very fast substring search algorithm. Communications of the ACM, 33(8), 132–142. https://doi.org/10.1145/79173.79184