P9778 [HUSTFC 2023] Gene Editing

Qiyue has $n$ DNA base sequences $S_1, S_2, \dots, S_n$. Each base sequence can be represented as a string containing only the four uppercase letters `A`, `C`, `G`, and `T`. Qiyue can splice two DNA base sequences. The specific operation is: take a prefix (possibly empty) of the first sequence and concatenate it with a suffix (possibly empty) of the second sequence. For example, splicing `ACGC` and `CTAT` may produce `ACGCTAT`, `ACGCCTAT`, `ACAT`, or `T`. Based on this, Qiyue defines that a triple $(i, j, k)$ is good if and only if $1 \le i, j, k \le n$, $i \ne k$, $j \ne k$, and splicing $S_i$ and $S_j$ can produce $S_k$. Qiyue wants to know the number of good triples.

The first line contains an integer $n\ (3 \le n \le 2 \times 10^5)$, representing the number of base sequences. The next $n$ lines each contain a string. The $i$-th string defines the base sequence $S_i\ (1 \le |S_i| \le 2 \times 10^6)$. It is guaranteed that $\sum |S_i| \le 2 \times 10^6$.

Output one integer, representing the number of good triples.

Translated by ChatGPT 5