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

yukicoder #515: 典型LCP

事前に文字列を辞書順にソートしておく。
l番目の文字列とr番目の文字列のLCPをlcp(l, r)のように表すことにする。
|lcp(l, r)| <= |lcp(l+1, r)|
が成り立つから
lcp(l, r)
= lcp(lcp(l, l+1), lcp(l+1, r))
よって、長さx以下のprefixについて、lcp(i, j)を求める問題をlcp(x, i, j)とすると、各クエリは(∞, l, r)のように表せて
(∞, l, r)
= (|lcp(l, l+1)|, l+1, r)
= (min(|lcp(l, l+1)|, |lcp(l+1,l+2)|), l+2, r)
= ...
= (min[l<=i<=r-1](lcp(i, i+1)), r, r)
したがって、事前に隣接する文字列のLCP、lcp(i, i+1)をすべて求めておけば、RMQで解が求まる。

広告を非表示にする