Boyer Moore Algorithm for Pattern Searching Hard 0 attempts
GeeksforGeeks ↗

Boyer Moore Algorithm for Pattern Searching

Hard StringHash Table GeeksforGeeks

Implement the Boyer-Moore pattern searching algorithm. Given a text and a pattern, find all occurrences of the pattern in the text.

Example: text = "ABAAABCD", pattern = "ABC" → Output: [4]

Sample Input
—
Sample Output
—
Constraints
  • 1 <= text.length <= 10^5
  • 1 <= pattern.length <= text.length
Test Cases
Case 1
Args: ["ABAAABCD","ABC"] Expected: [4]
Topics
StringHash Table

Boyer-Moore Bad Character Heuristic

Precompute bad character table to skip alignments.

function boyerMoore(text, pattern) {
  const m = pattern.length, n = text.length, result = [];
  const badChar = {};
  for (let i = 0; i < m; i++) badChar[pattern[i]] = i;
  let s = 0;
  while (s <= n - m) {
    let j = m - 1;
    while (j >= 0 && pattern[j] === text[s + j]) j--;
    if (j < 0) { result.push(s); s += (s + m < n) ? m - (badChar[text[s+m]] ?? -1) : 1; }
    else s += Math.max(1, j - (badChar[text[s+j]] ?? -1));
  }
  return result;
}

Time: O(n/m) best, O(nm) worst | Space: O(alphabet size)

Saved in this browser only. Private to you.

JavaScript