Boyer Moore Algorithm for Pattern Searching Hard 0 attempts
GeeksforGeeks ↗

Boyer Moore Algorithm for Pattern Searching

Hard StringHash Table GeeksforGeeks

Using the Boyer-Moore string-matching technique, locate every position in text where pattern appears as a substring, and return those starting indices.

Input Format
Implement boyerMoore(text, pattern). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
text = "ABAAABCD"
pattern = "ABC"
Output
[4]

Example 2

Input
text = "AAAAA"
pattern = "AAA"
Output
[0,1,2]
Constraints
  • 1 <= text.length <= 10^5
  • 1 <= pattern.length <= text.length
Test Cases (2)
Case 1
Args: ["ABAAABCD","ABC"] Expected: [4]
Case 2
Args: ["AAAAA","AAA"] Expected: [0,1,2]
Topics
StringHash Table

Boyer-Moore Bad Character Heuristic

Precompute bad character table to skip alignments.

javascript
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