AT_abc343_g.[ABC343G] Compress Strings

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定 $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$

输出格式

请输出一个整数，表示答案。

输入输出样例

输入#1
```
3
snuke
kensho
uk
```
输出#1
```
9
```
输入#2
```
3
abc
abc
arc
```
输出#2
```
6
```

输入#3

6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm

输出#3

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页