Struct SuffixArray

pub struct SuffixArray<T> { /* private fields */ }

Implementations

impl<T: Ord> SuffixArray<T>

pub fn new(pat: Vec<T>) -> Self

Examples found in repository

crates/library_checker/src/string/suffixarray.rs (line 11)

pub fn suffixarray(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, s: Chars);
    let n = s.len();
    let sa = SuffixArray::new(s);
    iter_print!(writer, @it (1..=n).map(|i| sa[i]));
}

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

pub fn number_of_substrings(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, s: Chars);
    let mut ans = s.len() * (s.len() + 1) / 2;
    let sa = SuffixArray::new(s);
    let lcp = sa.longest_common_prefix_array();
    for x in lcp {
        ans -= x;
    }
    writeln!(writer, "{}", ans).ok();
}

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

Examples found in repository

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

pub fn number_of_substrings(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, s: Chars);
    let mut ans = s.len() * (s.len() + 1) / 2;
    let sa = SuffixArray::new(s);
    let lcp = sa.longest_common_prefix_array();
    for x in lcp {
        ans -= x;
    }
    writeln!(writer, "{}", ans).ok();
}

pub fn range(&self, t: &[T], next: impl Fn(&T) -> T) -> Range<usize>

Trait Implementations

impl<T: Clone> Clone for SuffixArray<T>

fn clone(&self) -> SuffixArray<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for SuffixArray<T>

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

Formats the value using the given formatter.

impl<T> Index<usize> for SuffixArray<T>

type Output = usize

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.