Struct SuffixAutomaton 

pub struct SuffixAutomaton { /* private fields */ }

A suffix automaton (DAWG) built online from a byte string.

Construct it with SuffixAutomaton::new; the build is O(n log |Σ|) for the BTreeMap transition tables (O(n |Σ|) with array tables). The automaton stores the length of the source string so that occurrence counts and the distinct-substring total can be reported directly.

Examples

use oxicuda_seq::string::SuffixAutomaton;

let sam = SuffixAutomaton::new(b"abcbc");
assert!(sam.contains(b"bcb"));
assert!(!sam.contains(b"acb"));
// "abcbc" has 12 distinct non-empty substrings.
assert_eq!(sam.distinct_substring_count(), 12);

Implementations

impl SuffixAutomaton

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

Build the suffix automaton of s.

An empty s yields an automaton with only the initial state; all queries then behave consistently (no non-empty substring exists, the distinct count is zero).

pub fn contains(&self, pattern: &[u8]) -> bool

Return true iff pattern is a substring of the source string.

The empty pattern is a substring of every string (including the empty string), so this returns true for an empty pattern.

pub fn distinct_substring_count(&self) -> usize

Number of distinct non-empty substrings of the source string.

Equals Σ_v (len[v] − len[link[v]]) over all non-initial states v, because each state recognises exactly len[v] − len[link[v]] distinct substrings (the suffixes of its longest string down to, but excluding, its suffix-link length).

pub fn occurrences(&mut self, pattern: &[u8]) -> usize

Number of (possibly overlapping) occurrences of pattern in the source.

Returns 0 when pattern is not a substring. The empty pattern is reported as occurring source_len + 1 times (once at each gap), matching the usual convention.

This finalises the endpos counters on first use (and caches them), hence the &mut self receiver.

pub fn state_count(&self) -> usize

Number of states in the automaton, including the initial state.

pub fn clone_count(&self) -> usize

Number of clone states produced during construction.

Exposed so tests can confirm that an input which forces a split actually triggered the clone path.

pub fn source_len(&self) -> usize

Length of the source string the automaton was built from.

Trait Implementations

impl Clone for SuffixAutomaton

fn clone(&self) -> SuffixAutomaton

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SuffixAutomaton

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

Formats the value using the given formatter.