AT_abc343_g [ABC343G] Compress Strings
题目描述
给定 $N$ 个字符串 $S_1,S_2,\ldots,S_N$。
请你求出一个最短的字符串的长度，使得它包含所有 $S_1,S_2,\ldots,S_N$ 作为其子串。
这里，字符串 $S$ 包含字符串 $T$ 作为子串，指的是可以通过从 $S$ 的开头删除 $0$ 个或多个字符、从末尾删除 $0$ 个或多个字符，得到 $T$。
输入格式
输入通过标准输入按以下格式给出。
> $N$
> $S_1$
> $S_2$
> $\vdots$
> $S_N$
输出格式
请输出一个整数，表示答案。
说明/提示
## 限制条件
- $N$ 是整数。
- $1 \leq N \leq 20$。
- $S_i$ 是仅由小写英文字母组成的、长度至少为 $1$ 的字符串。
- $S_1,S_2,\dots,S_N$ 的总长度不超过 $2\times 10^5$。
## 样例解释 1
长度为 $9$ 的字符串 `snukensho` 包含了 $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$。
由 ChatGPT 4.1 翻译