Boyer-Moore Search

Problem

Return the index of the first occurrence of pattern in text using the bad-character heuristic of Boyer-Moore, or -1 if it is absent.

Preprocess the last occurrence of each character in the pattern, compare from the right, and shift by the larger of 1 and the mismatch index minus the last occurrence. Return -1 for an empty pattern.

Hint

Compared characters are skipped by moving the pattern so the bad character aligns with its last occurrence.

Test cases

case 1

in: ["HERE IS A SIMPLE EXAMPLE","EXAMPLE"]

expected: 17

case 2

in: ["abcabc","abc"]

expected: 0

case 3

in: ["abc","d"]

expected: -1

case 4

in: ["a","a"]

expected: 0

case 5

in: ["","a"]

expected: -1

Starter codePython

def boyer_moore_search(text, pattern):
    # Your code here
    pass

5 test cases · run your code against them in the editor