文字列検索アルゴリズム
について探し物をしていたら、よくまとまった資料を見つけた。（PowerPoint資料）
http://www-ikn.ist.hokudai.ac.jp/ikn-tokuron/LN_H16_IKNtokuron-pattern_matching.ppt
-
-
- -
-
bit-parallelismという手法があることを知った。
非決定性有限オートマトンを状態を１bitで表して、１ワードの中に３２状態（３２bitマシンの場合）を同時に保持させ、ビット演算を用いて複数の状態を同時並行で計算するという手法だということ。
有名なアルゴリズムにShift-Orというアルゴリズムがある。http://www-igm.univ-mlv.fr/~lecroq/string/node6.html
今、興味を持っているのは、BNDMというアルゴリズムで、検索文字列を反転させてsuffix automatonを作り、それをbit-parallelismを用いて計算するという方法。
http://www-igm.univ-mlv.fr/~lecroq/string/bndm.html
http://citeseer.ist.psu.edu/navarro01fast.html
