Skip to content

rabinKarp ​

Devuelve todos los offsets de byte zero-based donde pattern aparece en text. Las coincidencias de hash se verifican contra los bytes originales, por lo que las colisiones no producen resultados falsos.

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

const matches: usize[] = rabinKarp("ababa", "ba");
print(matches[0], matches[1]); // 1 3

Resultado para estudio ​

tyrus
interface RabinKarpInfo {
    text: string;
    pattern: string;
    matches: usize[];
    comparisonCount: usize;
    shiftCount: usize;
    windowCount: usize;
    hashCollisionCount: usize;
    textVerificationCount: usize;
}
tyrus
import { RabinKarpInfo, StringSearchInfo, rabinKarpInfo } from "tyrus:algorithm";
const info: RabinKarpInfo = rabinKarpInfo("ababa", "ba");
print(info.matches); // [1, 3]
print(info.windowCount); // 4
print(info.hashCollisionCount); // 0
print(info.textVerificationCount); // 2

La complejidad esperada es O(n + m), con espacio auxiliar O(1) aparte del resultado.