Struct SuffixAutomaton 

pub struct SuffixAutomaton {
    states: Vec<State>,
    last: usize,
}

Fields

states: Vec<State>

last: usize

Implementations

impl SuffixAutomaton

pub fn new() -> Self

Examples found in repository

crates/competitive/src/string/suffix_automaton.rs (line 95)

    fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
        let mut sa = SuffixAutomaton::new();
        sa.extend(iter);
        sa
    }

pub fn state_size(&self) -> usize

Examples found in repository

crates/competitive/src/string/suffix_automaton.rs (line 52)

    pub fn number_of_substrings(&self) -> usize {
        let mut total = 0;
        for state in 1..self.state_size() {
            let link = self.link(state);
            total += self.length(state) - self.length(link);
        }
        total
    }

pub fn transitions(&self, state: usize) -> &HashMap<usize, usize>

pub fn length(&self, state: usize) -> usize

Examples found in repository

crates/competitive/src/string/suffix_automaton.rs (line 54)

    pub fn number_of_substrings(&self) -> usize {
        let mut total = 0;
        for state in 1..self.state_size() {
            let link = self.link(state);
            total += self.length(state) - self.length(link);
        }
        total
    }

pub fn link(&self, state: usize) -> usize

Examples found in repository

crates/competitive/src/string/suffix_automaton.rs (line 53)

    pub fn number_of_substrings(&self) -> usize {
        let mut total = 0;
        for state in 1..self.state_size() {
            let link = self.link(state);
            total += self.length(state) - self.length(link);
        }
        total
    }

pub fn number_of_substrings(&self) -> usize

Examples found in repository

crates/library_checker/src/string/number_of_substrings.rs (line 25)

pub fn number_of_substrings_suffix_automaton(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, s: Bytes);
    let sa = SuffixAutomaton::from_iter(s.iter().map(|&c| c as usize));
    writeln!(writer, "{}", sa.number_of_substrings()).ok();
}

fn push(&mut self, c: usize)

Examples found in repository

crates/competitive/src/string/suffix_automaton.rs (line 104)

    fn extend<T: IntoIterator<Item = usize>>(&mut self, iter: T) {
        for c in iter {
            self.push(c);
        }
    }

Trait Implementations

impl Debug for SuffixAutomaton

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

Formats the value using the given formatter.

impl Default for SuffixAutomaton

fn default() -> Self

Returns the “default value” for a type.

impl Extend<usize> for SuffixAutomaton

fn extend<T: IntoIterator<Item = usize>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl FromIterator<usize> for SuffixAutomaton

fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self

Creates a value from an iterator.