Boyer-Moore

Lee MENOS de n caracteres. El algoritmo de grep. Recorre de derecha a izquierda; salta hacia adelante. Patrón más largo → búsqueda más rápida.

La regla del mal carácter

• Alinea el patrón; compara desde su extremo DERECHO hacia atrás
• ¿Mismatch en el carácter c del texto? Desliza para alinear la posición más a la derecha de c en el patrón
• ¿c no está en el patrón? Brinca la longitud COMPLETA del patrón más allá de él
• Los caracteres que el salto se brinca nunca se examinan

Míralo brincar

'z' y 'y' no están en abcd → brincos de longitud completa, saltándose caracteres sin leer. Azul = comparando · verde = sufijo coincidente · rojo = mismatch → salto.

Patrón más largo, menos examinaciones

KMP: plano ~n (lee todo). Boyer-Moore: DESCIENDE. m=64 → 24× menos examinaciones.

Los detalles finos

• Solo bad-char: peor caso O(n·m) → agrega la regla del buen sufijo (BM completo)
• Gana en grande con alfabetos GRANDES + patrones LARGOS; alfabeto chico → KMP compite
• La variante Horspool (solo bad-char) es la que traen las herramientas tipo grep
• Siempre max(1, shift) o se atora

Para llevar

Oportunista (saltar) vs parejo (KMP lee todo) — ten claro tu régimen. Texto real, alfabeto grande → Boyer-Moore. Por eso grep vuela. Trilogía de patrón único completa. Sigue: los suffix arrays indexan el TEXTO.