分数: 500 点
问题陈述
对于字符串 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).
约束
- 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
- 所有输入数字均为整数。
输入
输入由标准输入按以下格式给出:
N S_1 \ldots S_N
输出
打印答案。
样本输入 1
3 ab abc arc
示例输出 1
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.
示例输入 2
11 ab bb aaa bba baba babb aaaba aabbb a a b
示例输出 2
32