はじめに これは、3回にわけて Wu らによる O(NP) アルゴリズムを解説、実装するシリーズです。 ①仕組み、考え方 ②探索方法 ③Goによる実装 <- 今回 の3部に分かれています。 今回は、O(NP) アルゴリズムを実際に実装していきます。 前回(①仕組み、考え方)、前々回(②探索方法)でアルゴリズムの考え方、探索方法はわかっているので、今回は実装上の注意点を説明しつつ、実装していきます。 元論文は An O(NP) Sequence Comparison Algorithm by described by Sun Wu, Udi Manber and Gene Myers です。興味のある方はそちらも目を通すと面白いと思います。 最終的な実装を確認したい方は https://github.com/convto/onp に置いてあるのでそちらをごらんください。 これは Makuak

はじめに これは、3回にわけて Wu らによる O(NP) アルゴリズムを解説、実装するシリーズです。 ①仕組み、考え方 ②探索方法 <- 今回 ③Goによる実装 の3部に分かれています。 今回も、前回に引き続き Wu らによる O(NP) アルゴリズムの解説をしていきたいと思います。 前回の ①仕組み、考え方編 では、大まかな考え方を整理して、なぜ計算量が下がるのかわかりました。 今回は、前回わかったことを利用して、実際にどう探索していくのかまとめていきます。 元論文は An O(NP) Sequence Comparison Algorithm by described by Sun Wu, Udi Manber and Gene Myers です。興味のある方はそちらも目を通すと面白いと思います。 最終的な実装を確認したい方は https://github.com/convto/on

はじめに 今回はテキストの差分検出などで使われる Wu らによる O(NP) のアルゴリズムの解説をしつつ、後半ではGoで実装していこうと思います。 ざっくり書いてみたら量がめちゃめちゃ多かったので、いくつかに分けて投稿しました。 ①仕組み、考え方 <- 今回 ②探索方法 ③Goによる実装 の３部に分かれています。 元論文は An O(NP) Sequence Comparison Algorithm by described by Sun Wu, Udi Manber and Gene Myers です。気になる方はそちらもどうぞ。 最終的な実装を確認したい方は https://github.com/convto/onp に置いてあるのでそちらをごらんください。 これは Makuake Development Team Advent Calendar 2019 - Adventar の4