No.962 LCPs
polylogK
lumc_
問題文最終更新日: 2019-12-24 13:19:44
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Advent Calendar Contest 2019
(順位表)
の他の問題:
Problem Statement
For one or more strings, define the longest common prefix $\mathrm{LCP}(s_1, s_2, \cdots, s_K)$ as the longest string that is a prefix of all of $s_1, s_2, \cdots, s_K$.
You are given $N$ strings consisting of lowercase English letters. Find the following value.
- $\displaystyle{\sum_{L = 1}^{N} \sum_{R = L}^{N} |\mathrm{LCP}(S_L, S_{L + 1}, \cdots, S_R)| (R - L + 1)}$
- Here, for a string $T$, $|T|$ denotes the length of that string.
Input
$N$ $S_1$ $S_2$ $\vdots$ $S_N$
- $1 \le N \le 2 \times 10^5$
- $1 \le |S_i| \le 2 \times 10^5$
- $1 \le \displaystyle{\sum_i |S_i|} \le 2 \times 10^5$
- $S_i$ is a string consisting only of lowercase English letters.
Output
Output the value as an integer on one line.
Sample
Sample 1
Input
4 akane akari aoi po
Output
26
The LCP of the interval [1, 1] is akane, and its length is 5.
The LCP of the interval [1, 2] is aka, and its length is 3.
The LCP of the interval [1, 4] is the empty string, and its length is 0.
The answer is $(5 * 1 + 3 * 2 + 1 * 3 + 0 * 4) + (5 * 1 + 1 * 2 + 0 * 3) + (3 * 1 + 0 * 2) + (2 * 1) = 26$.
Sample 2
Input
5 a a a a a
Output
35
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。