Baeza-Yates-Gonnet-Algorithmus

Der Baeza-Yates-Gonnet-Algorithmus bzw. Shift-or-Algorithmus, der auch unter den Namen Shift-and oder Bitap bekannt ist, löst das String-Matching-Problem, indem er einen nichtdeterministischen Automaten simuliert. Unter anderem wird eine Abwandlung dieses Algorithmus bei dem Unix-Tool grep benutzt. Da die Implementierung auf Bit-Operationen zurückgeführt werden kann, ist der Algorithmus alleine von der Ausführung her bereits sehr effizient. Kombiniert man dies mit dem zu Grunde liegenden System (im Preprocessing einmal Schleife über das Muster, während der Suche einmal Schleife über den Text) ergibt sich ein extrem effizienter Algorithmus.