AT_abc353_e [ABC353E] Yet Another Sigma Problem

题目描述

对于字符串 $x, y$，定义 $f(x, y)$ 如下：

• $f(x, y)$ 为 $x, y$ 的最长公共前缀的长度。

给定 $N$ 个仅由小写英文字母组成的字符串 $(S_1, \ldots, S_N)$。请计算下式的值：

输入格式

输入以如下格式从标准输入读入：

$N$ $S_1$ $S_2$ $\ldots$ $S_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
ab abc arc

输出 #1

4

输入输出样例 #2

输入 #2

11
ab bb aaa bba baba babb aaaba aabbb a a b

输出 #2

32

说明/提示

限制条件

• $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$
• 输入的所有数值均为整数

样例解释 1

• $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$。

由 ChatGPT 4.1 翻译