分数: 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