[−][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 |