Struct SuffixArray 

pub struct SuffixArray { /* private fields */ }

A suffix array together with its source length and (lazily-built) LCP array.

Construct with SuffixArray::new. The stored sa is a permutation of 0..n (n = source length); SuffixArray::lcp returns the Kasai LCP array, and SuffixArray::search performs SA binary search.

Examples

use oxicuda_seq::string::SuffixArray;

let sa = SuffixArray::new(b"banana").expect("non-empty");
// Suffixes of "banana" sorted: a, ana, anana, banana, na, nana.
assert_eq!(sa.sa(), &[5, 3, 1, 0, 4, 2]);
assert_eq!(sa.search(b"ana"), vec![1, 3]);

Implementations

impl SuffixArray

pub fn new(s: &[u8]) -> SeqResult<Self>

Build the suffix array of s using SA-IS in linear time.

Errors

Returns SeqError::EmptyInput for an empty s: the suffix array of the empty string is empty and is rejected to keep the contract explicit and consistent with the sibling string modules.

pub fn sa(&self) -> &[usize]

Borrow the suffix array (a permutation of 0..n).

pub fn text(&self) -> &[u8]

Borrow the source text.

pub fn rank(&self) -> Vec<usize>

The rank (inverse suffix) array: rank[sa[i]] == i.

pub fn lcp(&self) -> Vec<usize>

Compute the Kasai LCP array in O(n).

The returned vector has length n; lcp[0] = 0 and, for 1 ≤ i < n, lcp[i] is the length of the longest common prefix of the suffixes text[sa[i-1]..] and text[sa[i]..].

pub fn distinct_substring_count(&self) -> usize

Number of distinct non-empty substrings of the source, n(n+1)/2 − Σ lcp.

Every substring is a prefix of exactly one suffix; summing suffix lengths counts all substrings with multiplicity, and the LCP between adjacent suffixes is precisely the number of duplicate prefixes to subtract.

pub fn search(&self, pattern: &[u8]) -> Vec<usize>

Find all occurrences of pattern via two binary searches on the suffix array, returning the matching text positions in ascending order.

Returns an empty vector for an empty pattern or when there is no match. Overlapping occurrences are all reported.

Trait Implementations

impl Clone for SuffixArray

fn clone(&self) -> SuffixArray

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SuffixArray

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.