Baby Stepsなブログ

競プロとか。間違ったこと書いてあったら@pi0nep1oneにご連絡ください。

2021-03-11から1日間の記事一覧

強連結成分分解の実装と個人的なメモ

前提 有向グラフGの頂点の部分集合をSとする。 Sが強連結であるとは、Sの任意の2頂点間が行き来可能であること Sが強連結成分であるとは、Sに他のどの頂点を追加してもそれ以上強連結にならないこと 強連結成分分解とは、強連結成分を1つの頂点にまとめるこ…

ダブリングによる接尾辞配列(Suffix-Array)の実装と個人的なメモ

AC Libraryに、より高速なライブラリが存在する。 https://atcoder.github.io/ac-library/document_ja/string.html 以下に載せた実装は、自分の理解を深めるために実装したもの。(蟻本のものにアレンジを加えclass化した。計算量は変わらず、Manber & Myers…