又一个 Sigma 问题

题目描述

对于字符串 $x$ 和 $y$,定义 $f(x, y)$ 如下:

$f(x, y)$ 为 $x$ 和 $y$ 的最长公共前缀的长度。

给定由小写英文字母构成的 $N$ 个字符串 $(S_1, \ldots, S_N)$。求以下表达式的值:

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j)$。

输入格式

输入按以下格式从标准输入给出:

$N$
$S_1$ $\ldots$ $S_N$

输出格式

输出答案。

样例

3
ab abc arc

4

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

11
ab bb aaa bba baba babb aaaba aabbb a a b

32

数据范围

• $2 \le N \le 3\times 10^5$
• $S_i$ 是由小写英文字母构成的字符串。
• $1 \le |S_i|$
• $|S_1|+|S_2|+\ldots+|S_N|\le 3\times 10^5$
• 输入中的所有数均为整数