読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

aoj2614:Almost Same Substring

解法

LCPを高速に求められるか聞かれているだけ。
ロリハ+二分探索を使えば、変なライブラリなどがなくても可能。しかし、SAを持っていれば終了(SAは変なライブラリではない)

S.size()=Nとおけば、SAの構築にはSA_ISを使っているので、圧倒的O(N)。(しかしこれは罠で、実はO(NlogN)。LCPの計算のために内部でRMQが必要になるが、sparse_tableだとMLEすることが多くて残念なので、segment_treeでやるようにしている)


後、はむこさんの回答をみたんですが、Z-algorithmを使えば楽にキチンとO(N)になるみたいですね。(一応知ってはいたが一度も使ったことがなかったので忘れてた)

SAにしてもロリハ二分探索にしてもなにかしら危険が伴うので、Z-algorithmでのLCPで十分ならこっちを使ったほうがよさそうですね

コード