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