Rabin-Karp法による複数文字列(パターン)検索を試す - Negative/Positive Thinking

はじめに 前から気になっていたRabin-Karp法による複数文字列検索を試しに書いてみた。 ここでいう問題は、「ある長い文字列の中に、複数の探したい部分文字列が含まれるかどうか、含まれる場合そのindexは？」を考える。 Rabin-Karp法 文字列探索するときに、ある部分の文字列が部分文字列と一致するかどうかにハッシュ値を使う方法 ハッシュ値には「ローリングハッシュ法」と呼ばれる、1文字ずらした時のハッシュ値を簡単・高速に求められる方法が使われる 単一の部分文字列検索の場合、他の探索手法(KMP法やBM法)の方が速かったりするので、あまり使われないが、複数の部分文字列検索の場合は効率的に探索できる アルゴリズムは、 探したい長さmの文字列subのハッシュ値を計算 文字列strの先頭から長さm分だけハッシュ値を計算 一致している場合は見つかったということなので、探索を終了する もし一致