Struct SuffixArray 

pub struct SuffixArray {
    sa: Vec<usize>,
}

Fields

sa: Vec<usize>

Implementations

impl SuffixArray

pub fn new<T>(text: &[T]) -> Self

where T: Ord,

Examples found in repository

crates/library_checker/src/string/suffixarray.rs (line 11)

pub fn suffixarray(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, s: Chars);
    let n = s.len();
    let sa = SuffixArray::new(&s);
    iter_print!(writer, @it (1..=n).map(|i| sa[i]));
}

crates/competitive/src/string/string_search.rs (line 71)

    pub fn new(text: Vec<T>) -> Self {
        let suffix_array = SuffixArray::new(&text);

        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
        let rmq = RangeMinimumQuery::new(lcp_array.clone());

        Self {
            text,
            suffix_array,
            lcp_array,
            rank,
            rmq,
        }
    }

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

    pub fn new(text: Vec<T>) -> Self {
        let n = text.len();
        let suffix_array = SuffixArray::new(&text);
        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
        builder.push_node(0, 0);
        let mut leafs = vec![!0; n + 1];
        leafs[0] = 0;
        let mut stack = Vec::with_capacity(n);
        stack.push(0);
        for i in 1..=n {
            let lcp = lcp_array[i - 1];
            let mut last_popped = !0;
            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
                last_popped = stack.pop().unwrap();
                builder.nodes[last_popped].sa_range.end = i;
            }

            // internal node
            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
                let parent = stack.last().cloned().unwrap();
                let internal = builder.nodes.len();
                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
                builder.detach_last_child(parent, last_popped);
                builder.attach_child(parent, internal);
                builder.attach_child(internal, last_popped);
                stack.push(internal);
            }

            // leaf node
            let parent = stack.last().cloned().unwrap();
            let leaf = builder.nodes.len();
            builder.push_node(n - suffix_array[i], i);
            builder.attach_child(parent, leaf);
            stack.push(leaf);
            leafs[i] = leaf;
        }
        while let Some(node) = stack.pop() {
            builder.nodes[node].sa_range.end = n + 1;
        }

        builder.reindex(&mut leafs[1..]);
        let children = builder.build_children();
        let inv = builder.build_aux(&children);
        let nodes = builder.nodes;
        let suffix_array = suffix_array.into_inner();

        Self {
            text,
            suffix_array,
            lcp_array,
            rank,
            nodes,
            children,
            leafs,
            inv,
        }
    }

pub fn into_inner(self) -> Vec<usize>

Examples found in repository

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

    pub fn new(text: Vec<T>) -> Self {
        let n = text.len();
        let suffix_array = SuffixArray::new(&text);
        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
        builder.push_node(0, 0);
        let mut leafs = vec![!0; n + 1];
        leafs[0] = 0;
        let mut stack = Vec::with_capacity(n);
        stack.push(0);
        for i in 1..=n {
            let lcp = lcp_array[i - 1];
            let mut last_popped = !0;
            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
                last_popped = stack.pop().unwrap();
                builder.nodes[last_popped].sa_range.end = i;
            }

            // internal node
            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
                let parent = stack.last().cloned().unwrap();
                let internal = builder.nodes.len();
                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
                builder.detach_last_child(parent, last_popped);
                builder.attach_child(parent, internal);
                builder.attach_child(internal, last_popped);
                stack.push(internal);
            }

            // leaf node
            let parent = stack.last().cloned().unwrap();
            let leaf = builder.nodes.len();
            builder.push_node(n - suffix_array[i], i);
            builder.attach_child(parent, leaf);
            stack.push(leaf);
            leafs[i] = leaf;
        }
        while let Some(node) = stack.pop() {
            builder.nodes[node].sa_range.end = n + 1;
        }

        builder.reindex(&mut leafs[1..]);
        let children = builder.build_children();
        let inv = builder.build_aux(&children);
        let nodes = builder.nodes;
        let suffix_array = suffix_array.into_inner();

        Self {
            text,
            suffix_array,
            lcp_array,
            rank,
            nodes,
            children,
            leafs,
            inv,
        }
    }

pub fn lcp_array_with_rank<T>(&self, text: &[T]) -> (Vec<usize>, Vec<usize>)

where T: PartialEq,

Examples found in repository

crates/competitive/src/string/suffix_array.rs (line 61)

    pub fn lcp_array<T>(&self, text: &[T]) -> Vec<usize>
    where
        T: PartialEq,
    {
        self.lcp_array_with_rank(text).0
    }

crates/competitive/src/string/string_search.rs (line 73)

    pub fn new(text: Vec<T>) -> Self {
        let suffix_array = SuffixArray::new(&text);

        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
        let rmq = RangeMinimumQuery::new(lcp_array.clone());

        Self {
            text,
            suffix_array,
            lcp_array,
            rank,
            rmq,
        }
    }

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

    pub fn new(text: Vec<T>) -> Self {
        let n = text.len();
        let suffix_array = SuffixArray::new(&text);
        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
        let mut builder = SuffixTreeBuilder::with_capacity(n * 2);
        builder.push_node(0, 0);
        let mut leafs = vec![!0; n + 1];
        leafs[0] = 0;
        let mut stack = Vec::with_capacity(n);
        stack.push(0);
        for i in 1..=n {
            let lcp = lcp_array[i - 1];
            let mut last_popped = !0;
            while builder.nodes[stack.last().cloned().unwrap()].depth > lcp {
                last_popped = stack.pop().unwrap();
                builder.nodes[last_popped].sa_range.end = i;
            }

            // internal node
            if builder.nodes[stack.last().cloned().unwrap()].depth < lcp {
                let parent = stack.last().cloned().unwrap();
                let internal = builder.nodes.len();
                builder.push_node(lcp, builder.nodes[last_popped].sa_range.start);
                builder.detach_last_child(parent, last_popped);
                builder.attach_child(parent, internal);
                builder.attach_child(internal, last_popped);
                stack.push(internal);
            }

            // leaf node
            let parent = stack.last().cloned().unwrap();
            let leaf = builder.nodes.len();
            builder.push_node(n - suffix_array[i], i);
            builder.attach_child(parent, leaf);
            stack.push(leaf);
            leafs[i] = leaf;
        }
        while let Some(node) = stack.pop() {
            builder.nodes[node].sa_range.end = n + 1;
        }

        builder.reindex(&mut leafs[1..]);
        let children = builder.build_children();
        let inv = builder.build_aux(&children);
        let nodes = builder.nodes;
        let suffix_array = suffix_array.into_inner();

        Self {
            text,
            suffix_array,
            lcp_array,
            rank,
            nodes,
            children,
            leafs,
            inv,
        }
    }

pub fn lcp_array<T>(&self, text: &[T]) -> Vec<usize>

where T: PartialEq,

Trait Implementations

impl Clone for SuffixArray

fn clone(&self) -> SuffixArray

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SuffixArray

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Index<usize> for SuffixArray

type Output = usize

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.