AT_abc353_e [ABC353E] Yet Another Sigma Problem

对于字符串 $x, y$，定义 $f(x, y)$ 如下： - $f(x, y)$ 为 $x, y$ 的最长公共前缀的长度。 给定 $N$ 个仅由小写英文字母组成的字符串 $(S_1, \ldots, S_N)$。请计算下式的值： $$ \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i, S_j) $$

输入以如下格式从标准输入读入： > $N$ $S_1$ $S_2$ $\ldots$ $S_N$

请输出答案。

### 限制条件 - $2 \leq N \leq 3 \times 10^5$ - $S_i$ 为仅由小写英文字母组成的字符串 - $1 \leq |S_i|$ - $|S_1| + |S_2| + \ldots + |S_N| \leq 3 \times 10^5$ - 输入的所有数值均为整数 ### 样例解释 1 - $f(S_1, S_2) = 2$ - $f(S_1, S_3) = 1$ - $f(S_2, S_3) = 1$ 因此，答案为 $f(S_1, S_2) + f(S_1, S_3) + f(S_2, S_3) = 4$。 由 ChatGPT 4.1 翻译