ローリングハッシュで各種文字列アルゴリズムと同じことをする
表記
文字列$ s に対して、$ l, l + 1, \ldots, r - 1 文字目を抜き出した部分文字列を$ s_{l..r} とする。
文字列$ sのハッシュを$ h(s)とする。
すべて前計算に文字列長に比例する時間かかる。
部分文字列検索
文字列$ Sが文字列$ Tを部分文字列として含むかの判定を$ O(|S| + |T|)で行える。
文字列$ Sの長さ$ |T|の部分文字列と、$ Tについてそれぞれハッシュを求める。
LCP
$ \text{LCP}(S, T)を$ O(\log \min \{ |S|, |T|\})で求める。
$ \max \{ n | h(S_{0 .. n}) = h(T_{0 .. n}) \} を二分探索で求める。
辞書順比較
$ Sと$ Tの大小比較を$ O(\log N)で行う。
$ i = \min \{ i | h(S_{0 .. i + 1}) \ne h(T_{0 .. i + 1}) \}を二分探索で求める。
$ i文字目を見るとわかる。
接尾辞とのLCP
Z Algorithmで求められるものと同じ。
$ \text{LCP}(S, S_{i..N})を$ O(N \log N)で計算する。
$ i = 0, 1, \ldots, N - 1 について、$ \max \{ n | h(S_{0..n}) = h(S_{i .. i + n}) \} を二分探索で求める。
隣接する接尾辞のLCP
LCP配列とも呼ばれるやつ。
$ \text{LCP}(S_{i .. N}, S_{i + 1 .. N})を$ O(N \log N)で計算する。
$ i = 0, 1, \ldots, N - 2 について、$ \max \{ n | h(S_{i..i + n}) = h(S_{i + 1 .. i + 1 + n}) \} を二分探索で求める。
接尾辞配列
接尾辞配列を$ O(N \log^2 N)で求める。(参考にあるのと同じ)
ソートするとき、文字列の比較をローリングハッシュ+二分探索で行う。
回文判定
左右反転した文字列のロリハと比較することにより$ O(1)で判定できる。
参考