Module suff_collections::tree

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

Examples

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

let word: &str = "Some word";
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::<u8>();
// let lcp: LCP<u16> = st.lcp::<u16>();
// let lcp: LCP<u32> = st.lcp::<u32>();
let lcp: LCP<usize> = st.lcp::<usize>();

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

// construct online suffix tree
let mut ost: OnlineSuffixTree = OnlineSuffixTree::new();

// add word to online suffix tree
ost.add(word);

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

// convert online suffix tree to suffix tree
let st: SuffixTree = ost.finish();

Structs

Node
NodeIdx
OnlineSuffixTree
SuffixTree