Skip to content

boyerMoore ​

Devuelve todos los offsets de byte zero-based donde pattern aparece en text, omitiendo comparaciones mediante un desplazamiento basado en el mal carácter.

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

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

Resultado de estudio ​

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]

El resultado de estudio ejecuta la misma búsqueda por mal carácter mientras registra cada comparación y desplazamiento aplicado. Su almacenamiento adicional es O(m + s), donde m es el tamaño del patrón y s es el número de alineaciones inspeccionadas.

La búsqueda usa tiempo O(nm) en el peor caso y espacio auxiliar O(1) para su tabla de bytes.