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で十分ならこっちを使ったほうがよさそうですね
