Suffix Collections

Fast realization of suffix array and suffix tree for substring search, longest common prefix array (lcp array).

Unicode

The current implementation builds suffix structures using bytes and does not decode the string before or during construction in Unicode. But if Unicode string is normalized before construction and search, then structures support Unicode (because all byte sequences are decoded unambiguously). Also search and lcp returns indexes as in byte array but not in Unicode decoded string.

Example

• SuffixTree ```rust 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 = st.find(find);

  // construct lcp // lcp[i] = maxpref(sa[i], sa[i - 1]) && lcp.len() == sa.len() // let lcp: LCP = st.lcpstack::(); // let lcp: LCP = st.lcpstack::(); // let lcp: LCP = st.lcpstack::(); // let lcp: LCP = st.lcpstack::(); let lcp: LCP = st.lcprec::();

  // convert suffix tree to suffix array // let sa = SuffixArray::::fromstack(st); // let sa = SuffixArray::::fromstack(st); // let sa = SuffixArray::::fromstack(st); // let sa = SuffixArray::::fromstack(st); let sa = SuffixArray::::from_rec(st);

  let mut buff = String::new(); SuffixTree::new("mississippi") .to_graphviz(&mut buff).unwrap(); println!("{}", &buff); ``` SuffixTree for the word "mississippi"

• SuffixArray ```rust 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::::new_stack(word); // let sa = SuffixArray::::new(word); // let sa = SuffixArray::::new(word); // let sa = SuffixArray::::new(word); let sa = SuffixArray::::new(word);

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

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

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

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

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

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

  let word = "mississippi"; let sa = SuffixArray::::new(word); let lcp = sa.lcp(); println!("LCP index suffixe's"); sa.iter().zip(lcp.iter()).foreach(|(&sa, &lcp)| { let suff = String::fromutf8( word.as_bytes()[sa as usize..] .iter().map(|&x|).collect::>() ).unwrap(); println!("{} {} {}", lcp, sa, suff); } ); ```

SuffixArray and lcp for the word "mississippi"

LCP index suffixe's 0 11 0 10 i 1 7 ippi 1 4 issippi 4 1 ississippi 0 0 mississippi 0 9 pi 1 8 ppi 0 6 sippi 2 3 sissippi 1 5 ssippi 3 2 ssissippi

All construction and search work for O(n). For the suffix tree implementation the Ukkonen algorithm is taken and for the suffix array implementation the SA-IS algorithm is taken.