P9089 "SvR-2" Work

Given $n$ strings **consisting of lowercase letters**, define the value of the $i$-th string as the number of its meaningful substrings (**if there are multiple essentially identical substrings, they are also counted multiple times**). A substring of the $i$-th string is meaningful if and only if it can be split into several strings, where each part is a suffix of any of the $n$ strings. Here is an example with $n=4$: ```plain int printf scanf ntnt ``` - For the string `printf`, the substring `intf` is meaningful, because it can be represented as `int` and `f`, which are suffixes of `int` and `scanf`, respectively. However, `rint` is not. - For the string `ntnt`, the substring `ntnt` is also meaningful, because it can be represented as `nt` and `nt` (both are the same suffix of `int`), or it can be represented as `ntnt`, which is a suffix of `ntnt`. Now, Little Z wants to know the sum of the values of these $n$ strings.

The first line contains an integer $n$. Then follow $n$ lines, each containing a string.

Output one integer in one line, representing the sum of the values.

#### Constraints **This problem uses bundled testdata and O2 optimization.** Let $s_i$ denote the length of the $i$-th string. | Subtask | Constraints / Special Properties | Score | | :------: | :------: | :------: | | $1$ | $n\le 3$, $\sum\limits \lvert s_i\rvert\le10$ | $5 \operatorname{pts}$ | | $2$ | $n=26$, each string consists of only one character | $5 \operatorname{pts}$ | | $3$ | $n=1$ | $15 \operatorname{pts}$ | | $4$ | $\sum\limits \lvert s_i \rvert \le 2000$ | $15 \operatorname{pts}$ | | $5$ | $\sum\limits \lvert s_i \rvert \le 2\times10^5$ | $30 \operatorname{pts}$ | | $6$ | $\sum\limits \lvert s_i \rvert \le 10^6$ | $30 \operatorname{pts}$ | For $100\%$ of the testdata, $1\le n \le 5\times10^5$, and $n\le \sum\limits \lvert s_i \rvert \le 10^6$. Translated by ChatGPT 5