Compress Strings

题目描述

给定 $N$ 个字符串 $S_1, S_2, \ldots, S_N$。 求一个包含所有这些字符串作为子串的字符串的最小可能长度。 这里，当且仅当可以通过从字符串 $S$ 的开头删除零个或多个字符并且从结尾删除零个或多个字符得到字符串 $T$ 时，称字符串 $S$ 包含字符串 $T$ 作为子串。

输入格式

输入从标准输入按如下格式给出： $N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

输出答案（一个整数）。

3
snuke
kensho
uk

9

3
abc
abc
arc

6

6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm

27

提示

$N$ 是一个整数。 $1 \leq N \leq 20$ $S_i$ 是由小写英文字母组成且长度至少为 $1$ 的字符串。 $S_1, S_2, \dots, S_N$ 的总长度最多为 $2\times 10^5$。字符串 $snukensho$ 长度为 $9$，包含 $S_1, S_2, S_3$ 作为子串。 具体地，$snukensho$ 的第 1 到第 5 个字符对应 $S_1$，第 4 到第 9 个字符对应 $S_2$，第 3 到第 4 个字符对应 $S_3$。 不存在更短的字符串能够包含 $S_1, S_2, S_3$ 作为子串。 因此，答案是 $9$。

标签: AtCoder|abc343G

来源

AtCoder|abc343G