Boyer–Moore pattern searching (bad-character rule)
Problem
Find every index where the pattern occurs in the text. Use the bad-character rule: on a mismatch, shift the pattern so that the mismatched text character lines up with its last occurrence in the pattern.
Example 1
Input: text = "ABAAABCD", pattern = "ABC" Output: [4]
Also asked as: Boyer Moore Algorithm for Pattern Searching
Test cases
Case 1
Input: "ABAAABCD", "ABC" Expected: [4]
Case 2
Input: "aaaa", "aa" Expected: [0,1,2]
Case 3
Input: "abc", "d" Expected: []
Case 4
Input: "ab", "abc" Expected: []
View solutionHide solution1 approach
1. Bad-character heuristic
Time O(n/m) best, O(n·m) worstSpace O(alphabet)
Align the pattern; compare right-to-left. On a mismatch, shift so the mismatched text char lines up with its last occurrence in the pattern (or past it).
function boyerMoore(text, pat) { const n = text.length, m = pat.length; const last = new Map(); for (let i = 0; i < m; i++) last.set(pat[i], i); const res = []; let s = 0; while (s <= n - m) { let j = m - 1; while (j >= 0 && pat[j] === text[s + j]) j--; if (j < 0) { res.push(s); // line the next text character up with its last occurrence, so overlapping matches are found s += s + m < n ? m - (last.has(text[s + m]) ? last.get(text[s + m]) : -1) : 1; } else { const lo = last.has(text[s + j]) ? last.get(text[s + j]) : -1; s += Math.max(1, j - lo); } } return res;}