Boyer-Moore compares pattern characters from right to left. It uses precomputed heuristics (bad character and good suffix) to skip ahead significantly, making it very fast in practice on long texts.
vector<int> boyerMoore(string t, string p) {
const int SIG = 256;
vector<int> last(SIG, -1), res;
for (int i = 0; i < (int)p.size(); i++) last[(unsigned char)p[i]] = i;
int n = t.size(), m = p.size(), s = 0;
while (s <= n - m) {
int j = m - 1;
while (j >= 0 && p[j] == t[s + j]) j--;
if (j < 0) {
res.push_back(s);
s += (s + m < n) ? m - last[(unsigned char)t[s + m]] : 1;
} else {
s += max(1, j - last[(unsigned char)t[s + j]]);
}
}
return res;
}Mismatches near the end produce bigger shifts than left-to-right methods.
Uses last occurrence map to decide shift distance quickly.
Excellent on large alphabets and long patterns in practice.
Quiz coming soon for this algorithm.