Background

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.

Problem Description

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$.)

Input Format

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}$.

Output Format

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$.

4
aa
ab
bac
caa

10
10

1
a

1
2

Hint

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