cp_library_rs/string/
suffix_array.rs

1//! 接尾辞配列（Manber-Myers法）
2
3macro_rules! cfor {
4    ($def:stmt ; $fin:expr ; $incr:stmt ;; $bl:block) => {{
5        $def
6        while $fin {
7            $bl
8            $incr
9        }
10    }}
11}
12
13/// SuffixArray
14pub struct SuffixArray;
15
16impl SuffixArray {
17    /// (rank[i], rank[i+k]) により比較する
18    fn ord(rank: &[isize], i: usize, k: usize) -> (isize, isize) {
19        (rank[i], *rank.get(i + k).unwrap_or(&-1))
20    }
21
22    /// 文字列Sの接尾辞配列を構築し，返す
23    /// - 時間計算量： $`O(|S| \log^2 |S|)`$
24    pub fn build(S: &str) -> Vec<usize> {
25        let N = S.len();
26        let mut rank: Vec<_> = S.chars().map(|c| c as isize).collect();
27        // 末尾（空文字列）
28        rank.push(-1);
29        let mut sa: Vec<_> = (0..=N).collect();
30
31        cfor! {let mut k = 1; k <= N; k *= 2;; {
32            // rankでソート
33            sa.sort_by_key(|&i| Self::ord(&rank, i, k));
34            // rankの更新
35            let mut tmp = vec![0; N + 1];
36            tmp[sa[0]] = 0;
37            for i in 1..=N {
38                tmp[sa[i]] = tmp[sa[i - 1]] +
39                    (Self::ord(&rank, sa[i - 1], k) < Self::ord(&rank, sa[i], k)) as isize;
40            }
41            rank = tmp;
42        }}
43        sa
44    }
45}
cp_library_rs/string/suffix_array.rs

cp_library_rs/string/
suffix_array.rs
