Algorithm Library

73 classic CS & problem-solving algorithms — highlighted C++ STL source plus a detailed explanation for each one.

73 / 73

Boyer-Moore

StringsO(n/m) avg, O(nm) worst · O(σ)

c++ · Boyer-MooreTime O(n/m) avg, O(nm) worstSpace O(σ)

1#include <bits/stdc++.h>
2using namespace std;
3 
4// Bad-character heuristic. Returns first match index, or -1.
5int boyerMoore(const string& text, const string& pat) {
6    int n = text.size(), m = pat.size();
7    if (m == 0) return 0;
8    vector<int> bad(256, -1);
9    for (int i = 0; i < m; ++i) bad[(unsigned char)pat[i]] = i;
10    int s = 0;
11    while (s <= n - m) {
12        int j = m - 1;
13        while (j >= 0 && pat[j] == text[s + j]) --j;
14        if (j < 0) return s;
15        s += max(1, j - bad[(unsigned char)text[s + j]]);
16    }
17    return -1;
18}

How it works

Scans the pattern right-to-left at each text position. On a mismatch, the bad-character table tells us how far we can safely shift the pattern based on the offending text character — often skipping many positions at once.

When to use it

›Searching long texts for a fixed pattern (grep-style tools).
›Pattern matching where the alphabet is large (ASCII / UTF-8 bytes).
›Cases where you want sub-linear average time without preprocessing the text.

Time complexity

O(n/m) avg, O(nm) worst

Space complexity

O(σ)

Worked example

text = "HERE IS A SIMPLE EXAMPLE", pat = "EXAMPLE" → returns 17. After comparing "EXAMPLE" against "SIMPLE_" and mismatching on the space, the shift table jumps the pattern past the mismatch in one step.