Struct SuffixArray 

pub struct SuffixArray { /* private fields */ }

A suffix array built from a text.

The suffix array stores the starting positions of all suffixes of the input text, sorted in lexicographic order. This enables efficient substring search via binary search.

Implementations

impl SuffixArray

pub fn build(text: &[u8]) -> Self

Build a suffix array from the given text using the SA-IS algorithm.

Appends a sentinel character (value 0, lexicographically smallest) to ensure correct suffix ordering.

Time complexity: O(n) where n is the length of the text.

Example

use cyanea_seq::suffix::SuffixArray;

let sa = SuffixArray::build(b"banana");
let positions = sa.search(b"banana", b"ana");
assert_eq!(positions.len(), 2);

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

Search for all occurrences of pattern in text.

The text must be the same text used to build the suffix array (without the sentinel). Returns positions in arbitrary order.

Time complexity: O(m log n) where m is the pattern length and n is the text length.

pub fn len(&self) -> usize

Number of entries in the suffix array (text length + 1 for sentinel).

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.