The Boyer –Moore algorithm

The Boyer-Moore algorithm is a powerful pattern matching algorithm that is known for its efficiency in searching for patterns within a text. It uses a combination of preprocessing and matching rules to skip unnecessary comparisons, making it faster than the Brute force and other traditional algorithms in many cases.

When the Mismatched Character of the Input Text is Present in the Pattern (Bad Character Rule):

we have found a mismatch between the character R of the text (the bad character) and the character C of the pattern. So, we will shift the pattern string until the character R of the pattern matches the character R of the text string.

When the Mismatched Character of the Input Text is Not Present in the Pattern (Good Suffix Rule):

There is a mismatch between G and Q, but G is not at all present in the entire pattern string. So, we would not compare the entire pattern and we would easily shift the pattern until the character G on the input text as:

The Boyer –Moore algorithm Algorithm in Python

Here's an example of the Boyer-Moore algorithm implemented in Python:

def boyer_moore(text, pattern):

    n = len(text)

    m = len(pattern)

    last_occurrence = {}  # Bad character table

    # Preprocessing phase: populate the bad character table

    for i in range(m):

        last_occurrence[pattern[i]] = i

    # Searching phase

    i = 0

    while i <= n - m:

        j = m - 1

        # Match pattern from right to left

        while j >= 0 and pattern[j] == text[i + j]:

            j -= 1

        if j == -1:

            # Pattern found at index i

            print("Pattern found at index", i)

            i += m


            if text[i + j] in last_occurrence:

                # Shift pattern to align with the last occurrence of the bad character

                shift = j - last_occurrence[text[i + j]]


                # Shift pattern to align with the entire pattern

                shift = j + 1

            i += shift

# Example usage


pattern = "RPCRQ"

boyer_moore(text, pattern)