P16628 [GKS 2017 #E] Copy & Paste
题目描述
你想要构造一个特定的目标字符串 $S$，它仅由小写英文字母组成。初始时你有一个空字符串，并且允许执行以下操作：
- 在字符串末尾添加任意一个小写字母。
- 将字符串中的任意子串（即从字符串中某个起始位置到某个结束位置之间的所有字符）复制到剪贴板。执行此操作会覆盖剪贴板中原有的内容。剪贴板初始为空。
- 将剪贴板的**全部**内容添加到字符串末尾（剪贴板内容不变）。
请问构造目标字符串所需的最少操作次数是多少？注意，你必须精确地构造出目标字符串，不能有多余的字母。
输入格式
输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个目标字符串 $S$。
输出格式
对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是构造目标字符串所需的最少操作次数（如题目描述所述）。
说明/提示
样例 #1 的最优解法为：
1. 输入 `a`。
2. 输入 `b`。
3. 输入 `c`。
4. 复制 `ab` 到剪贴板。
5. 在字符串末尾粘贴 `ab`。
6. 在字符串末尾粘贴 `ab`。
样例 #2 的最优解法为：
1. 输入 `a`。
2. 输入 `a`。
3. 输入 `a`。
4. 复制 `aaa` 到剪贴板。
5. 在字符串末尾粘贴 `aaa`。
6. 复制 `aaaaa` 到剪贴板。
7. 在字符串末尾粘贴 `aaaaa`。
### 限制条件
$S$ 仅由小写英文字母 a 到 z 组成。
**小数据集（测试集 1 – 可见）**
$1 \le T \le 100$。
$1 \le$ $S$ 的长度 $\le 6$。
**大数据集（测试集 2 – 隐藏）**
$1 \le T \le 100$。
$1 \le$ $S$ 的长度 $\le 300$。
翻译由 DeepSeek V4 Pro 完成