LCP
AtCoder
AtCoder500点
ABC-F
黄色diff
LCP
SuffixArray
文字列問題
prefixとsuffix
条件の言い換え
O(N^2)個のものを考える問題
stack
入れ子構造
非自明な線形時間
priority_queue
ランレングス圧縮
ならし計算量解析
ヒストグラム
区間
各kに対して
前処理
左右からそれぞれ走査する
差分更新
変数変換して扱いやすい同型な問題を見出す
累積和
これを機会に SA-IS を整備した! 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…