← 返回题目列表

AtCoder · abc353_e

H. 又一个西格玛问题

中文机器翻译题面 查看原题

分数: 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