Struct MultipleSuffixTree 

pub struct MultipleSuffixTree<T>
where
    T: Ord + Clone,
{
    texts: Vec<Vec<T>>,
    offsets: Vec<usize>,
    tree: SuffixTree<Delimited<T>>,
    position_map: Vec<(usize, usize)>,
}

Fields

texts: Vec<Vec<T>>

offsets: Vec<usize>

tree: SuffixTree<Delimited<T>>

position_map: Vec<(usize, usize)>

Implementations

impl<T> MultipleSuffixTree<T>

where T: Ord + Clone,

pub fn new(texts: Vec<Vec<T>>) -> Self

pub fn texts(&self) -> &[Vec<T>]

pub fn suffix_array(&self) -> &[usize]

pub fn lcp_array(&self) -> &[usize]

pub fn rank(&self) -> &[usize]

pub fn node_size(&self) -> usize

pub fn node(&self, node_id: usize) -> &STNode

pub fn children(&self, node_id: usize) -> &[usize]

pub fn position_map(&self) -> &[(usize, usize)]

pub fn depth_range(&self, node_id: usize) -> Range<usize>

pub fn kth_substrings(&self) -> MultipleKthSubstrings<'_, T>

fn to_global_start(&self, text_idx: usize, pos: usize) -> usize

Examples found in repository

crates/competitive/src/string/suffix_tree.rs (line 577)

    pub fn index_of_distinct_substring(&self, (text_idx, range): (usize, Range<usize>)) -> u64 {
        debug_assert!(text_idx < self.tree.texts.len());
        debug_assert!(range.start < range.end && range.end <= self.tree.texts[text_idx].len());
        let m = range.len();
        let start = self.tree.to_global_start(text_idx, range.start);
        let sa_idx = self.tree.tree.rank[start];
        let leaf = self.tree.tree.leafs[sa_idx];
        let node = self.tree.tree.node_covering_depth(leaf, m);
        let parent_depth = self.tree.tree.nodes[self.tree.tree.nodes[node].parent].depth;
        let offset = m - (parent_depth + 1);
        self.prefix_distinct[node - 1] + offset as u64
    }

    pub fn index_of_substring(&self, (text_idx, range): (usize, Range<usize>)) -> u64 {
        debug_assert!(text_idx < self.tree.texts.len());
        debug_assert!(range.start < range.end && range.end <= self.tree.texts[text_idx].len());
        let m = range.len();
        let start = self.tree.to_global_start(text_idx, range.start);
        let sa_idx = self.tree.tree.rank[start];
        let leaf = self.tree.tree.leafs[sa_idx];
        let node = self.tree.tree.node_covering_depth(leaf, m);
        let parent_depth = self.tree.tree.nodes[self.tree.tree.nodes[node].parent].depth;
        let offset = m - (parent_depth + 1);
        let occ = self.tree.tree.nodes[node].sa_range.len() as u64;
        let occ_idx = (sa_idx - self.tree.tree.nodes[node].sa_range.start) as u64;
        self.prefix_total[node - 1] + offset as u64 * occ + occ_idx
    }