最近ロリハあんまり人気なくない？

TL; DR

ロリハ + にぶたんで \(O(\log(n))\) 時間で大小比較できるので、愚直に比較する代わりにそれを使ってソートして \(O(n\log(n)^2)\) 時間で構築できる。

おさらい

ロリハ

ロリハ (rolling hash) のおさらいを軽くしておきます。

基数 \(b\) と法 \(p\) を適当な方法で決めておきます。文字列 \( s = (s_0, s_1, \dots, s_{n-1})\) に対して数列 \( s' = (s'_i)_{i=0}^n\) を \(s'_i = \sum_{j=0}^{i-1} (s_j\cdot b^{i-j-1})\bmod p\) で定義します。

このとき、 \[ \begin{aligned} s'_0 &\equiv 0 \\ s'_1 &\equiv s_0 \\ s'_2 &\equiv b\cdot s_0 + s_1 \\ s'_3 &\equiv b^2\cdot s_0 + b\cdot s_1 + s_2 \\ s'_4 &\equiv b^3\cdot s_0 + b^2\cdot s_1 + b\cdot s_2 + s_3 \end{aligned} \] のようになります。重み？つき累積和みたいなイメージです。 \(s'_{i+1} = (b\cdot s'_i + s_i)\bmod p\) のようにして求められるので、\(s\) から \(s'\) は \(O(n)\) 時間で構築できます。このとき、文字列 \(s\) のハッシュ値を \(s'_n\) とします。

このとき、\(s\) の区間 \([l, r)\) の部分文字列 \(s_{l, r} = (s_l, s_{l+1}, \dots, s_{r-1})\) のハッシュ値は \( (s'_r-s'_l\cdot b^{r-l})\bmod p\) で求められます。 \(b^i\) (\(0\le i\le n\)) を \(O(n)\) 時間で前計算しておくことで、この計算は \(O(1)\) 時間でできます。

これにより、部分文字列のペア \(s_{l, r}\) と \(s_{l', r'}\) が等しそうかどうかを \(O(1)\) 時間で判定できます。すなわち、\(s_{l, r}\) のハッシュ値と \(s_{l', r'}\) のハッシュ値が異なれば必ず \(s_{l, r}\ne s_{l', r'}\) だし、等しければそれなりの確率で \(s_{l, r} = s_{l', r'}\) です。確率の議論に関しては他の記事に任せます。ここが詳しそう*1。

必要に応じて複数の基数・法のペアを用意して計算することで、正しく判定できる確率は大きくできます。以下では、\(O(1)\) 時間で確率 \(1\) で正しく判定できるものとします*2。

接尾辞配列

接尾辞配列 (suffix array; SA) は、文字列 \(s = (s_0, s_1, \dots, s_{n-1})\) に対して、接尾辞 \( (s_{0, n}, s_{1, n}, \dots, s_{n-1, n}, s_{n, n})\) を辞書順に並べた配列です。ただし、\(s_{n, n}\)*3 は空文字列です。また、実際には、文字列を陽に持つのではなく、開始位置の添字の配列として持つことが多いです。

たとえば、abracadabra に対する SA は、[11, 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2] となります。各添字に対応する接尾辞は次の通りです。

11 (empty)
10 a
 7 abra
 0 abracadabra
 3 acadabra
 5 adabra
 8 bra
 1 bracadabra
 4 cadabra
 6 dabra
 9 ra
 2 racadabra

接尾辞配列をお手軽に知りたいときはこのサイトが便利です。

つくるよ

接尾辞配列の応用に関しては他の記事とかに任せるとして、ここでは構築だけを考えます。

接尾辞配列を愚直に求めることを考えます。Rust での実装例です。

fn main() {
    let s = "abracadabra";
    let mut sa: Vec<_> = (0..=s.len()).collect();
    sa.sort_unstable_by_key(|&i| &s[i..]);
    println!("{:?}", sa);  // [11, 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2]
}

C++ の例も載せておきます。

#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>

int main() {
  std::string s = "abracadabra";
  std::vector<size_t> sa(s.length() + 1);
  std::iota(sa.begin(), sa.end(), 0);
  std::sort(sa.begin(), sa.end(), [&](auto i, auto j) {
    return s.substr(i) < s.substr(j);
  });

  // 11 10 7 0 3 5 8 1 4 6 9 2
  for (size_t i = 0; i < sa.size(); ++i)
    std::cout << sa[i] << (i+1 < sa.size()? ' ': '\n');
}

最悪計算量について考えます。ソートの比較回数は \(\Theta(n\log(n))\) 回であり、比較に最悪 \(\Theta(n)\) 時間かかってしまうので、全体で \(O(n^2\log(n))\) 時間です*4。すべての文字が a の場合とかが最悪なはずです。

さて、ここの大小比較をロリハでやることで高速化しましょうというのが今回のお話です。ロリハの演算は \(O(1)\) 時間での ==/!= 判定ですが、これを \(O(\log(n))\) 時間での <=> 判定にします。要するに、\(\log(n)\) 倍悪くして大小比較までできるようにしましょうということです。

\(s\lt t\) のとき、ある \(i\) が存在して \(s_j = t_j\) (\(0\le j\lt i\)) かつ \(s_i\lt t_i\) です。なので、\(s_j = t_j\) (\(0\le j\lt i\)) なる最大の \(i\) をにぶたんで求め、\(s_i \lt t_i\) かどうかを判定すればよいです。

\(s_j = t_j\) (\(0\le j\lt i\)) は \(s_{0, i} = t_{0, i}\) に他ならないので、これはロリハで \(O(1)\) 時間でできます。にぶたんにより \(O(\log(n))\) 時間です。

よって、ソートの比較回数と併せて合計で \(O(n\log(n)^2)\) 時間です。