Struct SuffixArray

pub struct SuffixArray {
    pub sfx: Vec<usize>,
    pub rank: Vec<Vec<usize>>,
}

Suffix array data structure, useful for a variety of string queries.

Fields

sfx: Vec<usize>

The suffix array itself, holding suffix indices in sorted order.

rank: Vec<Vec<usize>>

rank[i][j] = rank of the j’th suffix, considering only 2^i chars. In other words, rank[i] is a ranking of the substrings text[j..j+2^i].

Implementations

impl SuffixArray

pub fn new(text: impl IntoIterator<Item = u8>) -> Self

Suffix array construction in O(n log n) time.

pub fn longest_common_prefix(&self, i: usize, j: usize) -> usize

Computes the length of longest common prefix of text[i..] and text[j..].