Bitapアルゴリズム
Shift-andアルゴリズムをRubyで実装した例と実行結果を以下に示す。このコードでは state が#アルゴリズムの表でのRに相当する。また、変数 pattern が表のパターンPに、変数 text が表のTに相当する。黄色の背景色でハイライトした部分がアルゴリズムの表で示したマッチング処理である。
実行結果(マッチした位置。0オリジンなので、アルゴリズムのセクションで言う9文字目は "8" で表される。)
acb+aca であれば、検索パターンを acbYaca とし、Yのビットが1なら acbYaca の二箇所のビットを1にする。Yのビットは0に戻しておく。
acb?aca であれば、検索パターンを acXbaca とし、Xのビットが1なら acXbaca の二箇所のビットを1にする。Xのビットは0に戻しておく。