Bitapアルゴリズム
以上の説明はshift-and型のバリエーションを前提としている。ブール代数の双対性により、このアルゴリズムにはshift-or型のバリエーションがある。shift-orアルゴリズムでは、shift-andアルゴリズムにおけるビットを反転させた上でビット単位のORで探索を行う。すなわち、#実装例のRubyコードの state(#アルゴリズムの表のR)の初期状態 (R0) は全て1が立っているビット列になり、文字列比較をしていた部分である
は
になる。state が使用するビット範囲の最上位ビットが0になったときにパターンとマッチする部分が発見されたことになる。
まとめると、shift-orでは実装例のコードの黄色でハイライトした部分が以下のように変更される。
mask[tc] をあらかじめビット反転しておけば、
としてやや効率化できる。Shift-andと比較すると、1とのビット単位のORを取る操作が減っているが、実際の性能への影響(例えばC言語実装が機械語にコンパイルされた時、実行速度がどの程度改善するか)は微妙だろう。