Skip to content

boyerMoore ​

Retorna todos os offsets byte zero-based onde pattern ocorre em text, pulando comparações por meio de um deslocamento baseado no mau caractere.

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

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

Resultado de estudo ​

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]

O resultado de estudo executa a mesma busca por mau caractere enquanto registra cada comparação e deslocamento aplicado. Seu armazenamento adicional é O(m + s), onde m é o tamanho do padrão e s é o número de alinhamentos inspecionados.

A busca usa tempo O(nm) no pior caso e espaço auxiliar O(1) para sua tabela de bytes.