AtCoder Beginner Contest 343
翻译中…
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.
翻译中…
样例
Input #1
3
snuke
kensho
uk
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$.
Input #2
3
abc
abc
arc
Output #2
6
Input #3
6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm
Output #3
27
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。