BM法による文字列マッチング学習メモ - $shibayu36->blog;grepで文字列マッチングしている時の仕組みを学ぶために、BM法などの文字列マッチングについて調べていた。調べたことをメモしておく。特にまとまってはいない。 参考になった文献は以下。 文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！ アルゴリズムの基本（7）（3/4 ページ） - ＠IT BM法をJSで実装している とりあえずイメージ掴むのには分かりやすい サービス終了のお知らせ BM法や、その亜種のHorspool のアルゴリズムとQuick-Searchを解説している ちょっとわかりづらいけど、一番ちゃんと書かれている すごく雑にイメージすると、 パターンの方に前処理を加えて、ある文字がパターンの中のどの位置にあるかを保存しておく パターンマッチングしていきマッチしなかった場合に、前処理で作った位置情報を使っていい感じにスキップする という感じ。雑すぎる。 BM法関連
