Bitap: el algoritmo de coincidencia de cadenas que se deriva de la fuerza bruta
Bitap: My favorite string matching algorithm
El algoritmo bitap, o shift-and, es una técnica de búsqueda de patrones que destaca por su simplicidad y eficiencia cuando el patrón es más corto que una palabra de máquina. A diferencia de Boyer-Moore o Knuth-Morris-Pratt, se deriva directamente del algoritmo ingenuo manteniendo un conjunto de estados activos y usando operaciones de bits para avanzar y filtrar transiciones. El autor lo prefiere por su elegancia conceptual y facilidad de implementación.
Aunque he estudiado Boyer-Moore y KMP en detalle, me lleva bastante tiempo derivarlos desde cero, mientras que bitap se deriva muy fácilmente, ya que para mí es solo el algoritmo ingenuo disfrazado de otra manera.