← 返回题目列表

AtCoder · awc0111_e

E. 招牌串联

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

分数: 433 分

问题陈述

高桥正尝试通过将多个标志连接成水平行来创建一条长横幅,作为文化节的装饰。他有 N 标志,以及 i-第一个符号有字符串 上面写着 S_i 。这里,字符串的长度(字符数) S_i 表示为 |S_i|.

高桥按照从 1-st 到 N,从左到右。连接它们时,为了节省空间,他尽可能地将相邻的标志重叠。

具体来说,当连接 i-第一个符号 (i \geq 2),他考虑正整数 l 满足以下有关字符串的所有条件 前一个符号的 S_{i-1} 和字符串 当前符号的 S_i :

  • 1 \leq l < |S_{i-1}| 和 l < |S_i|。 (也就是说,两个字符串都不完全包含在重叠中,并且每个字符串至少有 1 字符保留在重叠之外。)
  • 最后 l 的字符 S_{i-1} 匹配第一个 l 的字符 S_i.

如果这样一个正整数 l 存在,令 L_i 为其最大值。如果不存在,则让 L_i = 0.

连接时 i第一个标志,第一个 L_i 的字符 S_i 与前一个符号的末尾重叠。当 L_i = 0,它只是连接到末尾,没有任何重叠。无论哪种情况,新添加到横幅的字符数 S_i is |S_i| - L_i.

找到 字符总数 整个横幅的 整个横幅的当所有 N 符号按顺序连接(其中重叠部分仅计算一次)。

字符总数可以通过以下公式计算:

|S_1| + \sum_{i=2}^{N} (|S_i| - L_i)

示例

考虑以下情况 S_1 = abcabc 和 S_2 = abcxyz.

我们检查后缀之间的匹配 S_1 和前缀 S_2。由条件 l,我们有 1 \leq l < 6.当 l = 3,最后一个 3 的字符 S_1, abc,匹配第一个 3 的字符 S_2, abc。对于 l = 4, 5,没有匹配项。因此,最大 l 满足条件是 3,和 L_2 = 3.

连接结果为 abcabcxyz,总字符数为 6 + (6 - 3) = 9.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq |S_i| \leq 10^6
  • \displaystyle \sum_{i=1}^{N} |S_i| \leq 10^6
  • S_i 仅由小写英文字母组成。

输入

N
S_1
S_2
\vdots
S_N

第一行包含一个整数 N 代表符号的数量。在下文中 N 行, i- 第行 (1 \leq i \leq N) 包含字符串 S_i 写在 i-第一个标志。

输出

单行输出整个横幅的字符总数 N 符号按顺序连接,作为一个整数。 有


示例输入 1

3
abcabc
abcxyz
xyzabc

示例输出 1

12

示例输入 2

4
cat
dog
bird
fish

示例输出 2

14

示例输入 3

8
abracadabra
abraxyz
xyzxyz
yzalpha
alphabet
betamax
maximum
umami

示例输出 3

36

示例输入 4

20
aaaaab
abaaaa
aaaacaaa
caaad
aadbbb
bbbccc
cccdde
ddefgh
ghijklm
klmnop
opqrstu
stuvwx
vwxyzab
zabzab
abzabc
abcabcabc
bcabcx
xcdef
defdefg
fghello

示例输出 4

71

示例输入 5

1
a

示例输出 5

1