Log inSign up
hardLeetCodeNot Started

Boyer Moore Pattern Matching

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on LeetCode
Lesson

Problem Statement

Given two strings text and pattern, find the index of the first occurrence of pattern in text using the Boyer-Moore string search algorithm. If pattern is not part of text, return -1.

Demonstrate the Bad Character Rule heuristic for efficient lookahead skipping.

Example 1 · Example:

Input: text = "ABAAABCD", pattern = "ABC"
Output: 4
Explanation: Pattern "ABC" matches starting at index 4 ("ABAA[ABC]D").

Example 2 · Example:

Input: text = "HERE IS A SIMPLE EXAMPLE", pattern = "EXAMPLE"
Output: 17
Explanation: Pattern "EXAMPLE" begins at index 17.

Example 3 · Example:

Input: text = "leetcode", pattern = "leeto"
Output: -1
Explanation: "leeto" does not occur in "leetcode".

Constraints:

  • 1 <= text.length, pattern.length <= 10^5
  • text and pattern consist of standard ASCII characters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the core string patterns underlying Boyer Moore Pattern Matching.
  • Optimize time and space tradeoffs for string manipulation.
  • Handle string boundary conditions and unicode/ASCII edge cases.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Exact pattern substring search in large text bodies.
  • High-throughput pattern matching where skipping non-matching windows sub-linearly is critical.

Algorithmic Decision Tree:

  • Right-to-Left Pattern Scanning
  • Bad Character Table Shift Rule
  • Good Suffix Heuristic

Connected Patterns:

KMP Pattern MatchingRabin Karp Pattern MatchingImplement strStr

1. Naive Sliding Window Character Comparison

Intuition

1. For each starting index i from 0 to N - M: - Check if text[i + j] == pattern[j] for all 0 <= j < M. - If all characters match, return index i. 2. If no match is found after scanning all positions, return -1.

When to apply: Simple baseline for pattern search without preprocessing overhead.

Algorithm

  1. Iterate index i from 0 to N - M.
  2. Compare characters at text[i + j] with pattern[j].
  3. If mismatch, advance i by 1.
  4. If full match found, return i.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int strStr(std::string text, std::string pattern) {
7 int n = text.size(), m = pattern.size();
8 if (m == 0) return 0;
9 if (n < m) return -1;
10
11 for (int i = 0; i <= n - m; ++i) {
12 int j = 0;
13 while (j < m && text[i + j] == pattern[j]) {
14 j++;
15 }
16 if (j == m) return i;
17 }
18 return -1;
19 }
20};
21
22int main() {
23 Solution sol;
24 std::cout << sol.strStr("ABAAABCD", "ABC") << std::endl; // 4
25 std::cout << sol.strStr("HERE IS A SIMPLE EXAMPLE", "EXAMPLE") << std::endl; // 17
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O((N - M + 1) * M) — In worst case (e.g. text = "AAAAAAAAAB", pattern = "AAB"), checks M characters for every position: O(N * M).
  • Space complexity: O(1)

Why Brute Force Doesn't Scale:

Naive brute force re-examines already processed substrings multiple times.

For N = 105, O(N2) requires 1010 operations (TLE), while O(N) finishes in < 10ms.

2. Boyer-Moore-Horspool (Bad Character Rule Only)

Intuition

1. Build bad character table badChar of size 256 initialized to -1. 2. For each character pattern[i], record badChar[pattern[i]] = i. 3. Align pattern at shift = 0. 4. Compare pattern from right to left (j = M - 1 down to 0): - If all match, return shift. - If mismatch at j, advance shift += max(1, j - badChar[text[shift + j]]). 5. Repeat until shift > N - M.

When to apply: Practical, fast string matching in text editors and search utilities (grep/ripgrep).

Algorithm

  1. Precompute last occurrence index of each character in pattern.
  2. Start shift = 0.
  3. Compare from rightmost character of pattern backwards.
  4. On mismatch, shift pattern right by max(1, j - badChar[text[shift + j]]).
  5. If pattern matches completely, return shift index.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 int strStr(std::string text, std::string pattern) {
9 int n = text.size(), m = pattern.size();
10 if (m == 0) return 0;
11 if (n < m) return -1;
12
13 // Bad Character Heuristic Table
14 std::vector<int> badChar(256, -1);
15 for (int i = 0; i < m; ++i) {
16 badChar[(unsigned char)pattern[i]] = i;
17 }
18
19 int shift = 0;
20 while (shift <= n - m) {
21 int j = m - 1;
22
23 // Scan right to left
24 while (j >= 0 && pattern[j] == text[shift + j]) {
25 j--;
26 }
27
28 if (j < 0) {
29 return shift; // Match found
30 } else {
31 // Shift pattern
32 shift += std::max(1, j - badChar[(unsigned char)text[shift + j]]);
33 }
34 }
35 return -1;
36 }
37};
38
39int main() {
40 Solution sol;
41 std::cout << sol.strStr("ABAAABCD", "ABC") << std::endl; // 4
42 std::cout << sol.strStr("HERE IS A SIMPLE EXAMPLE", "EXAMPLE") << std::endl; // 17
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N / M) average, O(N * M) worst case — On random and natural language text, skips up to M characters per comparison, achieving O(N / M) average runtime.
  • Space complexity: O(Σ) where Σ is alphabet size (256)

3. Full Boyer-Moore Algorithm (Bad Character + Good Suffix Shift)

Intuition

1. Build Bad Character table badChar (size 256). 2. Build Good Suffix table goodSuffix (size M + 1) using suffix/prefix matching. 3. Compare pattern from right to left. 4. If match, return shift. 5. On mismatch at index j, shift is determined by max(badCharShift, goodSuffixShift[j + 1]). 6. This dual-heuristic avoids worst-case O(N * M) traps on repetitive alphabets.

When to apply: The definitive, industrial-grade implementation for pattern searching.

Algorithm

  1. Precompute Bad Character table and Good Suffix table.
  2. Align pattern at shift = 0.
  3. Scan pattern right-to-left.
  4. On mismatch, shift by max(bad_char_shift, good_suffix_shift).
  5. Return match index or -1.

Bad-Character Heuristic Right-to-Left Skipping

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [A, B, A, A, A, B, C, D]
Current operationSTEP 1 OF 6
Observation: Align pattern "ABC" at shift s = 0
Visual state
Values and pointers at this exact step
array
S
A
B
A
A
0
↑ Shift s=0
1
2
↑ Mismatch: txt[2]='A' vs pat[2]='C'
3
Variables at this step
shift
0
j
2
patChar
C
txtChar
A
badCharRule
Last 'A' in pat is at idx 0
skip
2
Why this step matters

Observation: Align pattern "ABC" at shift s = 0. Compare right-to-left: pat[2]='C' vs txt[2]='A'. Mismatch at txt[2].

Decision: Bad character 'A' appears at index 0 of pattern. Shift pattern right by max(1, j - badChar['A']) = max(1, 2 - 0) = 2.

Invariant: Boyer-Moore compares from right to left to maximize rightward skip distance.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7private:
8 std::vector<int> buildBadChar(const std::string& pat) {
9 std::vector<int> badChar(256, -1);
10 for (int i = 0; i < pat.size(); ++i) {
11 badChar[(unsigned char)pat[i]] = i;
12 }
13 return badChar;
14 }
15
16 std::vector<int> buildGoodSuffix(const std::string& pat) {
17 int m = pat.size();
18 std::vector<int> suff(m + 1, 0);
19 std::vector<int> goodSuffix(m + 1, m);
20
21 suff[m] = m;
22 int g = m, f = 0;
23 for (int i = m - 1; i >= 0; --i) {
24 if (i > g && suff[i + m - f] < i - g) {
25 suff[i] = suff[i + m - f];
26 } else {
27 if (i < g) g = i;
28 f = i;
29 while (g >= 0 && pat[g] == pat[g + m - f]) g--;
30 suff[i] = f - g;
31 }
32 }
33
34 int j = 0;
35 for (int i = 0; i < m; ++i) {
36 if (suff[i] == i + 1) {
37 for (; j <= m - 1 - i; ++j) {
38 if (goodSuffix[j] == m) goodSuffix[j] = m - 1 - i;
39 }
40 }
41 }
42 for (int i = 0; i < m - 1; ++i) {
43 goodSuffix[m - suff[i]] = m - 1 - i;
44 }
45 return goodSuffix;
46 }
47
48public:
49 int strStr(std::string text, std::string pattern) {
50 int n = text.size(), m = pattern.size();
51 if (m == 0) return 0;
52 if (n < m) return -1;
53
54 std::vector<int> badChar = buildBadChar(pattern);
55 std::vector<int> goodSuffix = buildGoodSuffix(pattern);
56
57 int shift = 0;
58 while (shift <= n - m) {
59 int j = m - 1;
60 while (j >= 0 && pattern[j] == text[shift + j]) {
61 j--;
62 }
63 if (j < 0) {
64 return shift;
65 } else {
66 int bcShift = std::max(1, j - badChar[(unsigned char)text[shift + j]]);
67 int gsShift = goodSuffix[j + 1];
68 shift += std::max(bcShift, gsShift);
69 }
70 }
71 return -1;
72 }
73};
74
75int main() {
76 Solution sol;
77 std::cout << sol.strStr("ABAAABCD", "ABC") << std::endl; // 4
78 std::cout << sol.strStr("HERE IS A SIMPLE EXAMPLE", "EXAMPLE") << std::endl; // 17
79 return 0;
80}

Time & Space Complexity

  • Time complexity: O(N + M) worst case, O(N / M) average — Preprocessing takes O(M + Σ) and search takes at most O(N) comparisons even in repetitive inputs due to the Good Suffix heuristic.
  • Space complexity: O(M + Σ) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive Sliding Window Character ComparisonO((N - M + 1) * M)O(1)Slide the pattern one character at a time across the text, comparing every character from left to right.Time / space complexity limits.
2.Boyer-Moore-Horspool (Bad Character Rule Only)O(N / M) average, O(N * M) worst caseO(Σ) where Σ is alphabet size (256)Precompute the bad character shift table from the pattern, scan characters from right to left, and jump forward by the bad character heuristic on mismatch.Time / space complexity limits.
3.Full Boyer-Moore Algorithm (Bad Character + Good Suffix Shift)OptimalO(N + M) worst case, O(N / M) averageO(M + Σ) auxiliaryCombines the Bad Character Heuristic and Good Suffix Heuristic, taking shift += max(badCharShift, goodSuffixShift) to guarantee worst-case linear time O(N + M) and sub-linear average time.Time / space complexity limits.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Scanning left-to-right instead of right-to-left: Boyer-Moore's major speed advantage relies strictly on comparing pattern characters from index M - 1 down to 0.

Pitfall 2:

Negative shift calculation: if bad character occurrence is to the right of current mismatch index j, j - badChar[...] is negative; taking max(1, ...) is essential.

Pitfall 3:

Not handling characters absent from the pattern (which should default to -1, enabling a full shift of j + 1).

Crucial Edge Cases to Validate:

  • Empty string or single character string.
  • String with duplicate or repeating characters.
  • Strings with different lengths or extreme character bounds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify character constraints (lowercase English only vs full Unicode/ASCII).
  2. Explain your choice of data structure (array frequency map vs hash table) before coding.
  3. Walk through a concrete small example during the dry run.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time complexity for Boyer Moore Pattern Matching?

Back to DSA Sheet