えびちゃんの日記

えびちゃん(競プロ)の日記です。

2021-08-01から1ヶ月間の記事一覧

ロリハを知っている人のための接尾辞配列

最近ロリハあんまり人気なくない? TL; DR ロリハ + にぶたん で \(O(\log(n))\) 時間で大小比較できるので、愚直に比較する代わりにそれを使ってソートして \(O(n\log(n)^2)\) 時間で構築できる。 おさらい ロリハ ロリハ (rolling hash) のおさらいを軽く…