Bitapアルゴリズム
挿入2文字目が現れた場合、state[0](更新前)のn - 1文字目のビットはすでに0になっているので state[1] のn - 1文字目のビットは1にならない。つまり、state[1] は1文字の挿入まで許容した検索となる。
state[2] は state[1] と同様の処理だが、ORするのは state[1] の更新前の値となる。挿入2文字目が現れた場合、state[1](更新前)のn - 1文字目のビットはまだ1なので、state[2] のn - 1文字目のビットは1になる。つまり state[2] は2文字の挿入まで許容した検索となる。同様にして state[3], state[4], ... を実装することで、許容する挿入文字数を増やした検索が可能になる。
#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。
state[0] でも rstr_mask とのORを行っているが、この時の rstr_mask の値は0なので state[0] の値は変化しない。
例えば#アルゴリズムのビットマスクに於いて、二文字目はaでもcでも良いという場合にはaのビットマスク(101001)を101011に変更すればよいだけであるため、容易に大文字小文字を無視する等の拡張ができる。 またレーベンシュタイン距離(以下、距離という)を管理することで、距離がパターン文字列に近い文字列を検索するあいまい検索が可能となる。
本来の状態を管理するビット列(#実装例に於けるstate)を距離ゼロ用とし、他に距離1用、距離2用など任意の検出したい最大の距離までのビット列を用意する。以降、距離 i 用の状態管理ビット列を state[i] と表現する。また、以下の文章と図では、AND・ORは特に注記しないかぎりビット単位のAND・ORを意味する。