えびちゃんの日記

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