Module suff_collections::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);

Structs

SuffixArray