Skip to content

boyerMoore ​

Returns every zero-based byte offset where pattern occurs in text, skipping comparisons with a bad-character shift.

tyrus
import { boyerMoore } from "tyrus:algorithm";

const matches: usize[] = boyerMoore("ababa", "aba");
print(matches[0], matches[1]); // 0 2

Study result ​

tyrus
interface BoyerMooreInfo {
    text: string;
    pattern: string;
    matches: usize[];
    comparisonCount: usize;
    shiftCount: usize;
    badCharacterTable: [usize, usize][];
    appliedShifts: usize[];
}
tyrus
import { BoyerMooreInfo, boyerMooreInfo } from "tyrus:algorithm";

const info: BoyerMooreInfo = boyerMooreInfo("ababa", "aba");
print(info.text); // ababa
print(info.pattern); // aba
print(info.matches); // [0, 2]
print(info.comparisonCount); // 7
print(info.shiftCount); // 3
print(info.badCharacterTable); // [[97, 2], [98, 1]]
print(info.appliedShifts); // [1, 1, 1]

The study result runs the same bad-character search while recording each comparison and applied shift. Its extra storage is O(m + s), where m is the pattern length and s is the number of inspected alignments.

The search uses O(nm) worst-case time and O(1) auxiliary space for its byte lookup table.