フューチャー夏休みの自由研究連載の5回目です。 はじめにTIG の辻です。 Go は標準ライブラリが充実しているとよく言われます。標準ライブラリだけで、HTTP サーバを作れたり、暗号化処理や、JSON や CSV といったデータ形式を扱うことができます。go list std | grep -v vendor | wc -l としてパッケージ数を見てみると、約 200 ものパッケージが存在することがわかります。本記事では、その多くの Go の標準ライブラリの中でも、個人的に面白いなと思ったライブラリを紹介したいと思います。suffixarray パッケージです。 suffixarray パッケージは Suffix Array を扱うライブラリです。suffixarray パッケージの魅力を感じるには、まず Suffix Array とは何か？ を知る必要があるでしょう。 Suffix A
A walk through the SA-IS Suffix Array Construction Algorithm¶ Some time ago, while looking for solutions to some string-searching problem I was having, I stumbled across the Suffix Array data-structure. It seemed promising, so I looked up the algorithm Wikipedia recommended (the “SA-IS” algorithm from the paper “Linear Suffix Array Construction by Almost Pure Induced-Sorting” by G. Nong, S. Zhang
競技プログラミングにおける文字列アルゴリズム問題まとめ [ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm,Palindromic Tree, Manacher, Suffix Tree] - はまやんはまやんはまやん
文字列アルゴリズム ローリングハッシュ 文字列をハッシュ化をするもの 詳しくはこっち Suffix Array 接尾辞配列 全文探索、パターンマッチングに使える LCP ある2つの文字列について接頭語がどれだけ一致しているか 複数文字列があるとき、ある任意の2つのLCPを求めたい場合は、「1.文字列を昇順ソート」「2.隣り合う文字列でLCPを計算」「3.ある任意の2つの間のLCPの中で最小のLCPがその2つの文字列のLCP」参考 KMP KMP法 : 単一文字列のマッチングアルゴリズム KMP法の前処理の段階でできる配列を使うと、最短の周期が取得できる 出典 動的KMP？（変更可能なKMP？） Trie, Aho-Corasick Trie : 複数文字列から作った木 Aho-Corasick法 : 複数文字列のマッチングアルゴリズム 資料 Aho-Corasick法で作った木に対してDP
![競技プログラミングにおける文字列アルゴリズム問題まとめ [ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm,Palindromic Tree, Manacher, Suffix Tree] - はまやんはまやんはまやん](https://cdn-ak-scissors.b.st-hatena.com/image/square/f34934dcc871419e07daf5367aeed4ef438323d0/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F10328537792368951407%2F10328749687230373352%2F1584199546)
Nyaan’s Library
Nyaan's Library このライブラリは競技プログラミング用に作成したアルゴリズム・データ構造をまとめたものです。 バグや解説の誤りなどを発見した方がいましたらこちらからご一報いただけると助かります。 動作確認はg++/C++17で行っています。また、一部のライブラリはavx2命令が実行できる環境でのみ動作します。 Library Files data-structure Binary Indexed Tree(Fenwick Tree) (data-structure/binary-indexed-tree.hpp) Binary Trie (data-structure/binary-trie.hpp) data-structure/divide-interval.hpp 動的Binary Indexed Tree (data-structure/dynamic-binary-
典型アルゴリズムそのままの問題はここOnline Programming Lesson ・エラトステネスの篩 アジア地区2002A ・連立合同式(ライツアウト系) PCK2006 アジア地区2010D 解説 夏合宿2008day2J(mod7,ジャッジ未対応) ・2点を通る半径rの円 国内予選2004D ・円と円の交点 国内予選2012E(線分の交差判定も) 解説 国内予選2013E 解説 ・円と円の共通接線 模擬国内2010E ・点と線分の距離 PCK2006 ・線分と線分の距離 国内予選2008E 模擬国内2012D ・ccw PCK2004予選11 ・凸包 PCK2004本選41 ・ボロノイ図 夏合宿2009day2F 解説 ・ローリングハッシュ Cf166div2D PROBLEMSET271D Editorial ・Z algorithm Cf246div2D PROBLEMSE
Luzhiled’s Library
Luzhiled's Library ぽよぽよぷりん バグっていたらごめんなさい バグを見つけたらスルーするか Issue またはプルリクを投げてください Bundle を押すと依存しているライブラリが全部展開されることを最近知ってびっくりしました Library Files dp/ Cumulative Sum 2D(二次元累積和) (dp/cumulative-sum-2d.hpp) Cumulative Sum(一次元累積和) (dp/cumulative-sum.hpp) Divide And Conquer Optimization (dp/divide-and-conquer-optimization.hpp) Edit Distance(編集距離) (dp/edit-distance.hpp) Knapsack 01(0-1ナップサック問題) $O(N \sum {v_i})
この記事はISer Advent Calendar 2019の1日目として書かれました。 最近ライブラリの剪定をしているときに「そういえばWavelet Matrix実装してないなぁ」と思ったので実装してみたら想像以上にシンプルで驚いたのでそれについての軽い解説を書きました。競プロ方面への応用については色んな方が記事を書いているので、後半ではWavelet Matrixの全文検索への応用としてFM-indexの話をします。 Wavelet Matrixとは Wavelet Tree 完備辞書(簡潔ビットベクトル) Wavelet Treeの計算量 Wavelet Matrix 各クエリの実装 FM-indexとは Suffix Array Burrows Wheeler 変換 LF mapping FM-index 実装 性能の比較 感想 Wavelet Matrixとは データ構造を知る
新歓ブログリレー2020 38日目の記事です。 競技プログラミングに役に立つかもしれないアルゴリズムのSuffix Array Induced Sorting(SA-IS)を構築する話をします。 @idatenに触発されて書きました（やったぁ） SA-ISってなに SA-ISとは高速でSuffix Array（接尾辞配列）構築するアルゴリズムです。 Suffix Arrayを作ると何がうれしいかと言うと、高速に全文検索ができるようになります。 また、SA-ISは Suffix Array Induced Sortingのそれぞれの頭文字をとったものからきているようです。 バイオインフォマティクスのDNAシーケンスの検索のときに使われるとか使われないとか… よくわからないんですけど。 接尾辞ってなに 接尾辞と言われてもよくわからないので説明します。 ある文字列Sの部分文字列の終端を同じくして
Suffix Array を作る - SA-IS の実装
Suffix Array は今若者の間で人気のデータ構造です． マイ suffix array を実装することで，オシャレ度がアップしてモテ系になり，女子力も上がると言われています． その中でも今特に，手軽でクールな SA-IS (アルファベットサイズ固定の下で線形時間で省メモリで suffix array が作れる今最強のアルゴリズム) の実装がブームです． 僕もブームに便乗して，実装してみました． ところで，SA-IS は流行っているので，日本語でもすでに様々なところで記事が書かれています (日付順)． SAIS(Suffix Array - Induced Sorting) - EchizenBlog-Zwei SA-IS: SuffixArray線形構築 - sileの日記 SA-IS - (iwi) ｛ 反省します - TopCoder部 接尾辞配列(Suffix Array)の
文字列アルゴリズムは世界を救う？Suffix Array と Longest Common Substrings｜株式会社レトリバ
文字列アルゴリズムは世界を救う？Suffix Array と Longest Common Substrings ※こちらの記事は、2020年6月2日にRetrieva TECH BLOGにて掲載された記事を再掲載したものとなります。 レトリバのCTOの武井です。（https://twitter.com/goth_wrist_cut ) 新型コロナウィルスが世界で猛威を振るっていますが、皆様安全に過ごせておりますでしょうか。 レトリバでは フルリモート化 や、 交流なども オンライン飲み会 にするなど、工夫して過ごしています。 さて、今回はそんな新型コロナウィルス、COVID-19の遺伝子配列をターゲットに、 Longest Common Substring(最長共通部分文字列)を求めたり、そのアルゴリズムの解説をしてみようと思います。 アルゴリズムの説明自体は William Fiset
AtCoderでレートが黄色になりました
AtCoderでレートが黄色になりました 最初の2年では2回しか参加していないので実質開始2年ほどでしょうか。黄色になりました。 黄色になったので記念にやったことを記していきます。 C#の仕様に詳しくなる C#はそれなりに高速でありながらも高級な記述力を持っているので、仕様に詳しくなると高速で汎用的な記述もできるようになります。 構造体をジェネリック型引数に渡すと実行時に高速というテクニックは筆頭です。 ライブラリを充実させる C#はライブラリを非常に書きやすい言語です。 過去問を解いていてライブラリ化できそうなものがあれば片っ端からライブラリ化しました。 下記の記事にライブラリの使い方をまとめています。 これまでに作ったライブラリ Mainメソッド(！？)(後述) Bit演算 PopCount, MSB, LSB ParallelBitDeposit(Intel Intrinsics の
Suffix Arrayは実際に文字列として配列は持つ必要はなく、開始位置の配列を保持することになります。このようなSuffix Arrayがあれば部分文字列の検索が高速に行えます。 例えば、"bra" という文字列を含むかどうか判定するには上記のようなSuffix Arrayを構築し、二分探索してやれば存在するか判定できますし、その開始位置もわかります。さらに複数含む場合そのすべての開始位置も二分探索で列挙できます。つまり、文字列Sが文字列Tを含むかどうかの判定は、計算量 O(MlogN) で行えるということです。(M=|T|, N=|S|) ただし問題点は Suffix のソートにあります。通常のソート(クイックソートなど)を使って愚直にソートすると、N=|S|としたとき、計算量 O(N2logN) かかります。ソートの計算量が O(NlogN) で文字列の比較1回につき O(N) か
![Suffix Array の解説と実装方法[C#][C++]](https://cdn-ak-scissors.b.st-hatena.com/image/square/9995db2e2d03c1442105256c5cb27e36bff56b8e/height=288;version=1;width=512/https%3A%2F%2Fwebbibouroku.com%2Fwp-content%2Fuploads%2F2016%2F07%2Fcsharp_log-710x410.png)
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GoとSuffixArray | フューチャー技術ブログ
A walk through the SA-IS algorithm - Screwtape's Notepad
ライブラリverify用問題集 - hirokazu1020の日記
Wavelet MatrixとFM-index - okura diary
SA-ISで高速にSuffix Arrayを構築する話【新歓ブログリレー 38日目】
Suffix Array の解説と実装方法[C#][C++]