Boyer-Moore y lo que medimos en una entrevista técnica

Recuerdo una entrevista técnica particularmente mala en la que me pidieron contar cuántas veces aparecía una cadena de caracteres dentro de un texto. Pude desarrollar una solución en pseudocódigo, aunque no fuera la más eficiente. Pero no conocía el algoritmo de Boyer-Moore y no conseguí avanzar mucho más.

No tengo claro cuánto debería pesar ese desconocimiento al evaluar a un candidato. La pregunta puede aportar información al entrevistador. Otra cosa es que toda la prueba termine girando alrededor de un algoritmo concreto.

Qué aporta Boyer-Moore

La solución más directa consiste en probar el patrón en cada posición del texto y comparar sus caracteres. Funciona, pero puede repetir muchas comparaciones.

Boyer-Moore busca evitar parte de ese trabajo. Compara el patrón de derecha a izquierda y aprovecha los desajustes para desplazarlo varias posiciones, en lugar de avanzar siempre de una en una. Para decidir esos saltos, utiliza información calculada previamente sobre el patrón.

Por ejemplo, si buscamos casa y el carácter situado al final de una ventana del texto es una x, sabemos que esa x no puede coincidir con ninguna posición del patrón. Podemos saltar toda esa ventana.

El algoritmo completo combina dos reglas de desplazamiento, conocidas como la del mal carácter y la del buen sufijo. Para mostrar la idea sin extender demasiado el código, podemos usar Boyer-Moore-Horspool, una variante más sencilla.

Un ejemplo pequeño en Rust

Esta implementación prepara una tabla de saltos y cuenta también las apariciones que se solapan:

fn contar(texto: &str, patron: &str) -> usize {
    let t = texto.as_bytes();
    let p = patron.as_bytes();
    let m = p.len();

    if m == 0 || m > t.len() {
        return 0;
    }

    let mut saltos = [m; 256];
    for j in 0..m - 1 {
        saltos[p[j] as usize] = m - 1 - j;
    }

    let mut posicion = 0;
    let mut total = 0;

    while posicion <= t.len() - m {
        let mut j = m;
        while j > 0 && p[j - 1] == t[posicion + j - 1] {
            j -= 1;
        }

        if j == 0 {
            total += 1;
        }

        posicion += saltos[t[posicion + m - 1] as usize];
    }

    total
}

fn main() {
    println!("{}", contar("bananana", "ana")); // 3
}

La tabla indica cuánto avanzar según el byte que ocupa el extremo derecho de la ventana. Si ese byte no aparece en el patrón, el salto es igual a la longitud del patrón. Si aparece antes de su última posición, el desplazamiento permite alinearlo con su aparición más a la derecha.

El ejemplo busca coincidencias exactas sobre bytes UTF-8, no equivalencias lingüísticas ni posiciones en caracteres. Además, adopta explícitamente la convención de devolver cero cuando el patrón está vacío.

Saber un algoritmo no es lo mismo que saber programar

Entender esta técnica resulta útil. Mi duda no está en el valor del algoritmo, sino en convertir su reproducción en una pizarra en el centro de una entrevista.

No podemos esperar que todos los candidatos conozcan todos los algoritmos y sean capaces de escribirlos de memoria. Si ese es el criterio decisivo, corremos el riesgo de incentivar una preparación centrada en adivinar qué algoritmo caerá, en lugar de aprender a programar mejor.

Una pregunta así puede servir para explorar cómo razona alguien: qué solución propone primero, dónde identifica trabajo repetido y cómo responde a una pista. Me parece más útil observar ese recorrido que hacer depender la evaluación de si el candidato recuerda el nombre y los pasos de Boyer-Moore.