103436: [Atcoder]ABC343 G - Compress Strings

Problem Statement

You are given $N$ strings $S_1, S_2, \ldots, S_N$.

Find the minimum length of a string that contains all these strings as substrings.

Here, a string $S$ contains a string $T$ as a substring if $T$ can be obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.

Constraints

• $N$ is an integer.
• $1 \leq N \leq 20$
• $S_i$ is a string consisting of lowercase English letters whose length is at least $1$.
• The total length of $S_1, S_2, \dots, S_N$ is at most $2\times 10^5$.

Input

The input is given from Standard Input in the following format:

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

Output

Print the answer as an integer.

Sample Input 1

3
snuke
kensho
uk

Sample Output 1

9

The string snukensho of length $9$ contains all of $S_1$, $S_2$, and $S_3$ as substrings.

Specifically, the first to fifth characters of snukensho correspond to $S_1$, the fourth to ninth correspond to $S_2$, and the third to fourth correspond to $S_3$.

No shorter string contains all of $S_1$, $S_2$, and $S_3$ as substrings. Thus, the answer is $9$.

Sample Input 2

3
abc
abc
arc

Sample Output 2

6

Sample Input 3

6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm

Sample Output 3

27

问题描述

给你 $N$ 个字符串 $S_1, S_2, \ldots, S_N$。

找出一个字符串，使其包含所有这些字符串作为子串的最短长度。

这里，字符串 $S$ 包含字符串 $T$ 作为子串，如果可以通过从 $S$ 的开头删除零个或多个字符，从 $S$ 的结尾删除零个或多个字符得到 $T$。

限制条件

• $N$ 是一个整数。
• $1 \leq N \leq 20$
• $S_i$ 是一个由小写英文字母组成的字符串，其长度至少为 $1$。
• $S_1, S_2, \dots, S_N$ 的总长度不超过 $2\times 10^5$。

输入

输入数据通过标准输入以以下格式给出：

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

将答案作为整数打印。

样例输入 1

3
snuke
kensho
uk

样例输出 1

9

长度为 $9$ 的字符串 snukensho 包含 $S_1$、$S_2$ 和 $S_3$ 作为子串。

具体来说，snukensho 的第一到第五个字符对应于 $S_1$，第四到第九个字符对应于 $S_2$，第三到第四个字符对应于 $S_3$。

没有更短的字符串包含 $S_1$、$S_2$ 和 $S_3$ 作为子串。因此，答案是 $9$。

样例输入 2

3
abc
abc
arc

样例输出 2

6

样例输入 3

6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm

样例输出 3

27