✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-199

Boyer-Moore Algorithm

Understand how Boyer-Moore accelerates pattern searching by comparing characters from right to left and skipping unnecessary text positions using mismatch information.

Explanation

Overview

Boyer-Moore is an efficient string-searching algorithm that compares the pattern with the text from right to left. When a mismatch occurs, it uses preprocessing information to shift the pattern by multiple positions instead of moving it forward one character at a time.

Key concepts

Right-to-left comparison; Bad-character heuristic; Good-suffix heuristic; Pattern preprocessing; Safe pattern shifting; Search optimization

Variables

text: The larger string being searched.; pattern: The pattern being located.; n: The length of the text.; m: The length of the pattern.; i: The current alignment position of the pattern in the text.; j: The pattern index currently being compared.

Complexity

preprocessing: Typically O(m + alphabetSize) for common table-based implementations, with details depending on the heuristic implementation.; searchAverage: Often sublinear in practice because it can skip multiple text positions.; worstCase: Depends on the exact Boyer-Moore variant and implementation; classical variants have different worst-case guarantees, while optimized variants can achieve linear worst-case behavior.; space: Depends on the alphabet size and preprocessing tables.

Example

text: HERE IS A SIMPLE EXAMPLE; pattern: EXAMPLE; explanation: Boyer-Moore begins comparisons at the rightmost character of the pattern. When a mismatch occurs, its heuristics can skip several positions based on the character and the already matched suffix.; result: Pattern found at index 17 using zero-based indexing.

Pseudocode

function boyerMoore(text, pattern):
preprocessBadCharacter(pattern)
preprocessGoodSuffix(pattern)
shift = 0
while shift <= length(text) - length(pattern):
j = length(pattern) - 1
while j >= 0 and pattern[j] == text[shift + j]:
j -= 1
if j < 0:
report shift
shift += safeMatchShift()
else:
badShift = badCharacterShift(text[shift + j], j)
goodShift = goodSuffixShift(j)
shift += max(1, badShift, goodShift)

Applications

Text editors.; Document searching.; Large text-file processing.; Search utilities.; Information retrieval.

Variables

Text

The larger string being searched.

Pattern

The pattern being located.

N

The length of the text.

M

The length of the pattern.

I

The current alignment position of the pattern in the text.

J

The pattern index currently being compared.

Shift

The number of positions by which the pattern moves after a mismatch.

Example or application

Text

HERE IS A SIMPLE EXAMPLE

Pattern

EXAMPLE

Explanation

Boyer-Moore begins comparisons at the rightmost character of the pattern. When a mismatch occurs, its heuristics can skip several positions based on the character and the already matched suffix.

Result

Pattern found at index 17 using zero-based indexing.

Definition

Boyer-Moore is an efficient string-searching algorithm that compares the pattern with the text from right to left. When a mismatch occurs, it uses preprocessing information to shift the pattern by multiple positions instead of moving it forward one character at a time.

Fundamental Heuristics

Bad Character Rule

Uses the mismatching text character and its last occurrence in the pattern to determine a safe shift.

Good Suffix Rule

Uses the portion of the pattern that matched before the mismatch to find another compatible occurrence or matching prefix.

Combined Rules

The algorithm commonly chooses the larger safe shift suggested by the bad-character and good-suffix rules.

Algorithm Steps

  • Preprocess the pattern to construct the bad-character information.

  • Preprocess the pattern to construct the good-suffix information when using the full algorithm.

  • Align the pattern with the current text position.

  • Compare characters from right to left.

  • If all characters match, record the occurrence.

  • If a mismatch occurs, calculate safe shifts using the available heuristics.

  • Move the pattern by the largest valid shift.

  • Repeat until the pattern cannot fit within the remaining text.

Pseudocode

function boyerMoore(text, pattern):
preprocessBadCharacter(pattern)
preprocessGoodSuffix(pattern)
shift = 0
while shift <= length(text) - length(pattern):
j = length(pattern) - 1
while j >= 0 and pattern[j] == text[shift + j]:
j -= 1
if j < 0:
report shift
shift += safeMatchShift()
else:
badShift = badCharacterShift(text[shift + j], j)
goodShift = goodSuffixShift(j)
shift += max(1, badShift, goodShift)

Complexity

Preprocessing

Typically O(m + alphabetSize) for common table-based implementations, with details depending on the heuristic implementation.

Search Average

Often sublinear in practice because it can skip multiple text positions.

Worst Case

Depends on the exact Boyer-Moore variant and implementation; classical variants have different worst-case guarantees, while optimized variants can achieve linear worst-case behavior.

Space

Depends on the alphabet size and preprocessing tables.

Key Concepts

  • Right-to-left comparison

  • Bad-character heuristic

  • Good-suffix heuristic

  • Pattern preprocessing

  • Safe pattern shifting

  • Search optimization

Advantages

  • Can skip multiple positions after a mismatch.

  • Often performs very well for long patterns and large alphabets.

  • Reduces unnecessary character comparisons in many practical cases.

  • Uses information from both mismatches and previously matched suffixes.

Limitations

  • The full algorithm is more complicated than naive matching.

  • Preprocessing may be unnecessary for very short patterns.

  • Performance depends on the text, pattern, alphabet, and selected variant.

  • Different implementations provide different worst-case guarantees.

Applications

  • Text editors.

  • Document searching.

  • Large text-file processing.

  • Search utilities.

  • Information retrieval.

Related Topics

  • Naive Pattern Matching

  • KMP Algorithm

  • Rabin-Karp Algorithm

  • Pattern Matching

Practice Question

In which direction does Boyer-Moore compare pattern characters?

Practice Answer

From right to left, beginning with the last character of the pattern.

Learning Objectives

  • Explain the central idea and purpose of boyer-moore algorithm.

  • Identify the assumptions, inputs, and conditions relevant to boyer-moore algorithm.

  • Evaluate an application of boyer-moore algorithm for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • String Algorithms and Pattern Matching

Suggest a correction or source · More in Algorithms & Data Structures