Skip to main content

library_checker/string/
number_of_substrings.rs

1use competitive::prelude::*;
2use competitive::string::{StringSearch, SuffixAutomaton};
3
4#[verify::library_checker("number_of_substrings")]
5pub fn number_of_substrings(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(s: Chars);
8    let n = s.len();
9    let search = StringSearch::new(s);
10    let mut ans = n * (n + 1) / 2;
11    for &x in search.lcp_array() {
12        ans -= x;
13    }
14    pp!(ans);
15}
16
17#[verify::library_checker("number_of_substrings")]
18pub fn number_of_substrings_suffix_automaton(reader: impl Read, writer: impl Write) {
19    prepare_io!(reader, writer);
20    sc!(s: Bytes);
21    let sa = SuffixAutomaton::from_iter(s.iter().map(|&c| c as usize));
22    pp!(sa.number_of_substrings());
23}