P6139 [Template] Generalized Suffix Automaton (Generalized SAM)

Admin note: This problem added the requirement to output the number of states on May 4, 2023. Solutions submitted before that did not output the number of states, hereby noted.

Given $n$ strings $s_1, s_2, \ldots, s_n$ consisting of lowercase letters, find the number of distinct substrings (excluding the empty string). Furthermore, let $Q$ be the minimal DFA that can accept all suffixes of $s_1, s_2, \dots, s_n$. Please output the number of states in $Q$. (If you cannot understand this sentence, you may treat it as outputting the number of states of the "generalized suffix automaton" built from $s_1, s_2, \dots, s_n$.)

The first line contains a positive integer $n$. The next $n$ lines each contain a string. The $i$-th line represents the string $s_{i-1}$.

The first line contains a positive integer: the number of distinct substrings. The second line contains a positive integer: the number of states in $Q$.

Constraints: $1 \le n \le 4 \cdot 10^5$, $1 \le \sum{|s_i|} \le 10^6$. Sample 1 explanation: There are $10$ distinct substrings: `"a","b","c","aa","ab","ac","ba","ca","bac","caa"`. The DFA structure is omitted. Sample 2 explanation: There is $1$ distinct substring: `"a"`. The DFA contains a start state $S$ and a state $T$, with an edge $S \to T$ labeled `a`. Therefore, the total number of states is $2$. Translated by ChatGPT 5