Suffix木
YosupoLibraryChecker
SuffixArray
蟻本例題
そのまま覚えたい典型問題
解空間:O(N^2)個のペア
連続部分列を扱う問題
文字列
復元
SuffixAutomation
Suffix木
prefixとsuffix
NoviSteps2D
2 つの文字列の最長の共通部分文字列 (部分列ではなく) を求める問題！ これ、蟻本の例題にもあるけど、POJ ではなく Yosupo Judge で解けるようになったのは大きい！ なお、Suffix Automation があれば本当に貼るだけみたい。 問題へのリンク 問題概要 2 つ…
AtCoder
AtCoder600点
ABC-Ex
銅色diff
SuffixArray
DFS
再帰的に上位桁から順に値で分類した木を作る
再帰的構造に着目する
文字列
制約:複数系列の長さの合計が10^5以下
クエリ処理問題
queue
応用的な探索
lcp
Cartesian木
Suffix木
セグメント木
解空間:O(N^2)通りの選択肢
連続部分列を扱う問題
prefixとsuffix
辞書順
K番目を求める
非自明な線形時間
N個の文字列の問題
NoviSteps5D
Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった！ 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…
