103534: [Atcoder]ABC353 E - Yet Another Sigma Problem
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：6
Solved：0
Description
Score: $500$ points
Problem Statement
For strings $x$ and $y$, define $f(x, y)$ as follows:
- $f(x, y)$ is the length of the longest common prefix of $x$ and $y$.
You are given $N$ strings $(S_1, \ldots, S_N)$ consisting of lowercase English letters. Find the value of the following expression:
$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j)$.Constraints
- $2 \leq N \leq 3\times 10^5$
- $S_i$ is a string consisting of lowercase English letters.
- $1 \leq |S_i|$
- $|S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5$
- All input numbers are integers.
Input
The input is given from Standard Input in the following format:
$N$ $S_1$ $\ldots$ $S_N$
Output
Print the answer.
Sample Input 1
3 ab abc arc
Sample Output 1
4
- $f(S_1,S_2)=2$
- $f(S_1,S_3)=1$
- $f(S_2,S_3)=1$
Thus, the answer is $f(S_1,S_2) + f(S_1,S_3) + f(S_2,S_3) = 4$.
Sample Input 2
11 ab bb aaa bba baba babb aaaba aabbb a a b
Sample Output 2
32
Output
得分：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