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 2Study 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.
