今日のアルゴリズム(JS実装)〜Rabin-Karp Algorithm〜

// どうも、わくばです！ 今回はRabin-Karp algorithmです。どんどん重たくなってきたので、日をまたがないとできなくなってきました(汗)。まだまだですね。。。 Rabin-Karp algorithmはハッシュ関数を用いたマッチングアルゴリズムです。ハッシュ関数というのは暗号化というか何らかの値を返す たとえば探している文字列をaaabとし、検索対象の文字列をabaaaaabaaababaabなどとした場合、まずは探したいaaabという文字列をハッシュ関数に掛け数値化(出力Xが得られたとする)します。そして 検索対象のアルゴリズムから、最初の4文字をとってきてハッシュ関数にか…

今日のアルゴリズム(JS実装)〜Knuth Morris Pratt Algorithm〜

// どうも、わくばです！ 今回はKMP algorithmです。これは意味がわかるまでかなり時間かかってしまいました。なんとなく言いたいことはわかるんですけど、それをアルゴリズムに起こすときにハテナが大量に(笑) KMPの探索部分はすぐしっくりきたんですが、Longest Proper Prefix which is Suffix (LPS) arrayをつくる部分が何をやってるのか全然わからなくて、、、(笑)。日本語の解説だとテーブルって呼んでるのも見かけますが、LPSと同じものです。 アルゴリズムそのものの解説はこの記事が非常にわかりやすいのでぜひ。 一週間で身につくアルゴリズムとデータ…

今日のアルゴリズム(JS実装)〜Naive String Pattern Matching〜

// どうも、わくばです！ 今日からPattern Searchingに入りたいと思います。KMP AlgorithmやBoyer Moore Algorithmなどちょっと耳にしたことのある仰々しい名前のアルゴリズムが待っているジャンルなのでちょっと怖いです(小並感)。 まずはNaive String Pattern Matchingです。Naiveと付くときは「モジュールやライブラリなどのサブルーチンを使うと簡単に実装できるけど、あえてそれを用いないで実装する」場合を指すことが多いです。今回は、多分正規表現使えば簡単にできるけど、それをNaiveに実装するという意味なのだと思います。シンプ…

今日のアルゴリズム(JS実装)〜Exponential Search〜

// どうも、わくばです！ 今日はExponential Searchです。Exponentialといのは指数関数的という意味です。理系学生は\(e^x\)や\(exp(x)\)でおなじみですよね。 このアルゴリズムは名前の通りで、指数関数的なインターバルを用いて飛び飛びに探索していくアルゴリズムです。Jump Searchと発想は近いと思いますが、Exponential Searchdでは最終的にBinary Searchを用いるので速いです。 以前記事にしたBinary Searchを添付しておきますので参考にしてみてください。 pyecracker99.hatenablog.com 以下…