Boyer–Moore pattern searching (bad-character rule)

Medium

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}