この土日のメモです. SAとLCPのお気持ちをまとめたくなっただけ. 間違ってたらごめん 文字列アルゴの勉強する気が起きないたった一つの理由: Rolling Hash— νιυεζ (@xiuez) 2019年12月13日 これをやめたいので, 手始めにSuffix Arrayを使った文字列検索をや…

この記事は「データ構造とアルゴリズム Advent Calendar 2019」 14日目の記事です. 13日目は@ajalabさんのRun-Length FM-Index - koki, 15日目は@minaminaoさんのMerkle Patricia Tree まわりです. toptreeとは toptreeは今年競プロ界隈で話題になった動的木…

niuez.github.io

niuez.hatenablog.com 引き続き, toptreeの解説をしていきます. Link link(v, w): 頂点vとwを辺vwで結ぶをします. 場合分けが多すぎるんじゃ が, vの次数が0, 1, 2以上で処理が変わり, またwの次数が0, 1, 2以上で処理が変わります. (ちなみに論文はどちらも…

みんな日本語記事を待っていたはず....! toptreeがどんな感じで動いているのかを書いてみます 実装はここにあります https://github.com/niuez/toptree-rust 0. toptree is なに toptreeはlink-cut treeの上位互換です. 木を切ったりつなげたり, パスのクエ…

読者層が限定されすぎていませんか？ Link Cut Treeを書いたことがない人はこちら！ ei1333.hateblo.jp 部分木クエリについてはこちら！ beet-aizu.hatenablog.com 最遠点クエリについてはこちら！ ei1333.hateblo.jp え〜っと, 多分toptreeが書けました. 多…

はじめまして, niuezといいます. 競プロを少ししています. 最近勉強したことのメモ書きをしておきます. ダイクストラ法 ダイクストラ法(Dijkstra)は負の長さの無いグラフで始点からの最短距離を求めるアルゴリズムです. 具体的には 距離が未確定の頂点の中で…