[][src]Crate suff_collections

no_std support

Suffix Array

Implementation of the suffix array construction of which is performed in linear time

Examples

    use suff_collections::{array::*, tree::*, lcp::*};

    // let word = "Some word";
    let word: &str = "Some word\0";
    let find: &str = "word";

    // construct suffix array
    // let sa = SuffixArray::<usize>::new_stack(word);
    // let sa = SuffixArray::<u8>::new(word);
    // let sa = SuffixArray::<u16>::new(word);
    // let sa = SuffixArray::<u32>::new(word);
    let sa = SuffixArray::<usize>::new(word);

    // construct lcp
    // lcp[i] = max_pref(sa[i], sa[i - 1]) && lcp.len() == sa.len()
    let lcp: LCP<usize> = sa.lcp();

    // finds the entry position of the line 'find' in 'word'
    // O(|find| * log(|word|))
    let res: Option<usize> = sa.find(find);

    // finds all the entry position of the line 'find' in 'word'
    // O(|find| * log(|word|))
    let res_all: &[usize] = sa.find_all(find);

    // finds the entry position of the line 'find' in 'word'
    // O(|word|)
    let res: Option<usize> = sa.find_big(&sa.lcp(), find);

    // finds all the entry position of the line 'find' in 'word'
    // O(|word|)
    let res_all: &[usize] = sa.find_all_big(&sa.lcp(), find);

    // convert suffix array to suffix tree
    let st = SuffixTree::from(sa);

Suffix Tree

Implementation of the suffix tree construction of which is performed in linear time

Examples

    use suff_collections::{array::*, tree::*, lcp::*};

    // let word = "Some word";
    let word: &str = "Some word\0";
    let find: &str = "word";

    // construct suffix tree
    let st: SuffixTree = SuffixTree::new(word);

    // finds the entry position of the line 'find' in 'word'
    let res: Option<usize> = st.find(find);

    // construct lcp
    // lcp[i] = max_pref(sa[i], sa[i - 1]) && lcp.len() == sa.len()
    // let lcp: LCP<u8> = st.lcp_stack::<u8>();
    // let lcp: LCP<u16> = st.lcp_stack::<u16>();
    // let lcp: LCP<u32> = st.lcp_stack::<u32>();
    // let lcp: LCP<usize> = st.lcp_stack::<usize>();
    let lcp: LCP<usize> = st.lcp_rec::<usize>();

    // convert suffix tree to suffix array
    // let sa = SuffixArray::<u8>::from_stack(st);
    // let sa = SuffixArray::<u16>::from_stack(st);
    // let sa = SuffixArray::<u32>::from_stack(st);
    // let sa = SuffixArray::<usize>::from_stack(st);
    let sa = SuffixArray::<usize>::from_rec(st);

Modules

array

Implementation of the suffix array construction of which is performed in linear time

lcp

lcp[i] = max_pref(sa[i], sa[i - 1]) and lcp.len() == sa.len()

tree

Implementation of the suffix tree construction of which is performed in linear time