Bitapアルゴリズム
ac(ba|ab)ca であれば、検索パターンを acZbaUabca とし、Zのビットが1なら acZbaUabca の二箇所のビットを立てる。またUのビットが立っていたら acZbaUabca のビットを1にする。ZとUのビットは0に戻しておく。
上記X, Y, Z, Uは実際の文字ではなく、ビット移動処理を行う場所を示すマーカーである。これらのビット移動処理はNFAで言えばεによる状態遷移に相当する。
取捨の実装例として、検索対象文字列 acaca からパターン acb?aca を検索する場合の動作を以下の表に示す。
上の表では、R2からR3への遷移について説明のために処理フェーズごとに分けて示している。#アルゴリズムの表と比較すると、上記Xの位置を示すビットマスクが追加されている。また、S0000000, S0000100は後述するSの値に応じてビットを1にする位置を示すビットマスクである。
Rに対して元のアルゴリズム通りにシフトと1のORを行う。その値をXのビットマスクとANDした結果をSとする。R3' (1)はR2に対してシフトと1のORを行った値である。R3' (1)とXのビットマスクのAND結果 (つまりS) は 0000100 になる。