Una cadena que empareja el algoritmo que mantiene una gran variedad de brocas, R, mostrando si los prefijos del patrón no coinciden en el lugar actual. Antes de buscar, desajuste matrices son computadas para cada carácter en el alfabeto y guardadas en una matriz, S. para la siguiente posición, con el carácter c, R = shift(R) o S(c). Si el último bit de R es 0, coincide con el patrón.