题目详情
返回题库题目描述
对于字符串x和y，定义f(x,y)如下：
- f(x,y)是x和y的最长公共前缀的长度。
给你一个由小写英文字母组成的N字符串(S1,…,SN)。求以下表达式的值：
$\sum_{i=1}^{N-1}$ $\sum_{j=i+1}^{N}$f($S_{i}$,$S_{j}$).
输入描述
第一行输入一个正整数N
第二行$S_{1}$,$S_{2}$,$S_{3}$，...$S_{N}$
数据范围：
- 2≤N≤3× $10^{5}$
- Si是一个由小写英文字母组成的字符串。
- 1≤∣Si∣
- ∣S1∣+∣S2∣+…+∣SN∣≤3×$10^{5}$
输出描述
输出答案
提示
样例1解释：
- f(S1,S2)=2
- f(S1,S3)=1
- f(S2,S3)=1
因此，答案为f(S1,S2)+f(S1,S3)+f(S2,S3)=4。