boyer moore with hash rodding

bmhr.py

from typing import Generator, Tuple, Dict
from collections import defaultdict

# Parámetros
L = 5  # longitud de la ventana de la "rod" (4-8 típico)
# Dos bases independientes de 64 bits (impares, apariencia aleatoria)
BASES = (11400714785074694791, 14029467366897019727)
MASK64 = (1 << 64) - 1  # máscara para emular overflow uint64

def _build_bad_char(pattern: str) -> dict:
    """
    Tabla de 'bad-character': para cada carácter, la última posición en el patrón.
    """
    table = {}
    for i, ch in enumerate(pattern):
        table[ch] = i
    return table

def _z_array(s: str):
    """
    Algoritmo Z para prefijos. Usado en la preprocesación del good-suffix.
    """
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    z[0] = n
    return z

def _build_good_suffix(pattern: str):
    """
    Construye la tabla de desplazamientos por good-suffix (regla fuerte).
    Devuelve shift[i] (desplazamiento cuando hay fallo en i).
    """
    m = len(pattern)
    shift = [m] * (m + 1)
    rev = pattern[::-1]
    z_rev = _z_array(rev)
    for j in range(m):
        if z_rev[j] > 0:
            i = m - z_rev[j]
            shift[i] = min(shift[i], j)
    z = _z_array(pattern)
    longest_prefix_len = 0
    for i in range(m - 1, -1, -1):
        if z[i] == m - i:
            longest_prefix_len = m - i
        shift[i] = min(shift[i], m - longest_prefix_len)
    return shift

def _rod_tuple_from_hashes(hashes: Tuple[int, int]) -> Tuple[int, int]:
    """
    Normaliza los hashes a 64 bits (emulación uint64) y devuelve la tupla rod.
    """
    return (hashes[0] & MASK64, hashes[1] & MASK64)

def _build_pattern_rods_bitsets(pattern: str, L: int = L) -> Dict[Tuple[int, int], int]:
    """
    Preprocesamiento de las 'rod':
    - Recorre el patrón y mantiene hashes rodantes (ventana de hasta L) con overflow 64-bit.
    - Para cada posición 'end' (índice final de la ventana en el patrón) calcula la rod (tupla de 2 hashes)
      y en el diccionario rods[rod] pone un bit 1 en la posición 'end' (bitset como int).
    - Resultado: mapping rod -> bitset con bits puestos en los índices finales donde aparece esa rod.
    Esto permite, en tiempo de búsqueda, saber rápidamente si existe una rod igual que termine
    en alguna posición ≤ j y calcular desplazamientos seguros.
    """
    m = len(pattern)
    rods = defaultdict(int)
    k = len(BASES)
    # powL[idx] = base^L mod 2^64 (usado para eliminar el carácter más antiguo de la ventana)
    powL = [pow(base, L, 1 << 64) for base in BASES]
    hashes = [0] * k
    window = []  # lista de valores ord() de la ventana actual (mantener hasta L)
    for end, ch in enumerate(pattern):
        cv = ord(ch)
        window.append(cv)
        # actualizar cada hash multiplicativo (emulación mod 2^64)
        for idx, base in enumerate(BASES):
            hashes[idx] = ((hashes[idx] * base) + cv) & MASK64
        if len(window) > L:
            # eliminar la contribución del carácter más antiguo usando powL
            old = window[-L-1]
            for idx in range(k):
                hashes[idx] = (hashes[idx] - (old * powL[idx])) & MASK64
            # recortar la ventana a los últimos L
            if len(window) > L:
                window = window[-L:]
        # crea la rod y setea el bit correspondiente al índice 'end'
        rod = _rod_tuple_from_hashes((hashes[0], hashes[1]))
        rods[rod] |= (1 << end)
    return dict(rods)

def _compute_text_rods_incremental(text: str, L: int = L):
    """
    Calcula las rods para cada posición final del texto (0..n-1) en O(n) mediante update incremental:
    - Mantiene los mismos hashes multiplicativos de 64 bits.
    - Remueve el carácter más antiguo usando powL para mantener ventana de longitud hasta L.
    Devuelve lista rods[pos] = rod_tuple para cada pos.
    """
    n = len(text)
    if n == 0:
        return []
    k = len(BASES)
    powL = [pow(base, L, 1 << 64) for base in BASES]
    hashes = [0] * k
    rods = [None] * n
    window = []
    for pos, ch in enumerate(text):
        cv = ord(ch)
        window.append(cv)
        for idx, base in enumerate(BASES):
            hashes[idx] = ((hashes[idx] * base) + cv) & MASK64
        if len(window) > L:
            old = window[-L-1]
            for idx in range(k):
                hashes[idx] = (hashes[idx] - (old * powL[idx])) & MASK64
            if len(window) > L:
                window = window[-L:]
        rods[pos] = _rod_tuple_from_hashes((hashes[0], hashes[1]))
    return rods

def boyer_moore_with_rods_fast(text: str, pattern: str, L_param: int = L) -> Generator[int, None, None]:
    """
    Búsqueda Boyer–Moore mejorada con 'hash rods' y mapeo rod->bitset:
    - Preprocesa bad-char, good-suffix y pattern_rods (rod -> bitset).
    - Precalcula rods del texto incrementalmente (O(n)).
    - En cada fallo en j (comparando desde la derecha), consulta la rod del texto en t = i + j:
        * Si esa rod no existe en pattern_rods: podemos desplazar la cantidad j+1 (mover más allá del fallo).
        * Si existe, usamos el bitset para comprobar si hay algún índice final q ≤ j donde esa rod
          coincide en el patrón. Si no hay ninguno, igualmente podemos desplazar j+1.
        * Si hay uno o más q ≤ j, tomamos el q mayor (más cercano a j) y calculamos un skip conservador:
          skip = (j - q) + 1. También respetamos bad-char y good-suffix: skip = max(skip, bc_shift, gs_shift).
    - Esta lógica garantiza que no se omite ninguna coincidencia real.
    """
    n, m = len(text), len(pattern)
    if m == 0:
        for i in range(n + 1):
            yield i
        return
    if n < m:
        return

    bad_char = _build_bad_char(pattern)
    good_suffix = _build_good_suffix(pattern)
    pattern_rods = _build_pattern_rods_bitsets(pattern, L=L_param)
    text_rods = _compute_text_rods_incremental(text, L=L_param)

    i = 0
    while i <= n - m:
        j = m - 1
        # comparar de derecha a izquierda como en Boyer–Moore clásico
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:
            # coincidencia completa
            yield i
            i += good_suffix[0]
        else:
            t = i + j
            text_rod = text_rods[t]
            if text_rod is None or text_rod not in pattern_rods:
                # no hay rod igual en el patrón: podemos desplazar j+1 (mover más allá del fallo)
                skip = j + 1
            else:
                bitset = pattern_rods[text_rod]
                # máscara para considerar solo posiciones q <= j
                mask = (1 << (j + 1)) - 1
                relevant = bitset & mask
                if relevant == 0:
                    # no existen rods iguales terminando en indices ≤ j -> podemos saltar j+1
                    skip = j + 1
                else:
                    # existe al menos un q ≤ j; escogemos el mayor (más cercano a j)
                    q = relevant.bit_length() - 1
                    # Para pasar ese candidato necesitamos (j - q) + 1
                    skip = (j - q) + 1
                    # respetar reglas clásicas también
                    bc_shift = j - bad_char.get(text[t], -1)
                    gs_shift = good_suffix[j + 1]
                    skip = max(1, skip, bc_shift, gs_shift)
            i += max(1, skip)

# Prueba rápida
if __name__ == "__main__":
    txt = "HERE IS A SIMPLE EXAMPLE EXAMPLE"
    pat = "EXAMPLE"
    print(list(boyer_moore_with_rods_fast(txt, pat, L_param=4)))  # esperado [17, 25]