103436: [Atcoder]ABC343 G - Compress Strings
Description
Score: $600$ points
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
Input
Output
问题描述
给你 $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