Function bio::data_structures::suffix_array::shortest_unique_substrings

pub fn shortest_unique_substrings<SA: SuffixArray>(pos: &SA, lcp: &LCPArray) -> Vec<Option<usize>>

Calculate all locally shortest unique substrings from a given suffix and lcp array (Ohlebusch (2013). "Bioinformatics Algorithms". ISBN 978-3-00-041316-2). Complexity: O(n)

Arguments

• pos - the suffix array
• lcp - the lcp array

Returns

An vector of the length of the shortest unique substring for each position of the text. Suffixes are excluded. If no unique substring starts at a given position, the entry is None.

Example

use bio::data_structures::suffix_array::{suffix_array,lcp,shortest_unique_substrings};
let text = b"GCTGCTA$";
let pos = suffix_array(text);

// obtain compressed LCP array
let lcp = lcp(text, &pos);

// calculate shortest unique substrings
let sus = shortest_unique_substrings(&pos, &lcp);
assert_eq!(sus, [Some(4), Some(3), Some(2), Some(4), Some(3), Some(2), Some(1), Some(1)]);