题解 | #小红的字符串#

题目链接

小红的字符串

题目描述

给定一个目标字符串 $S$ 。我们可以从一个空字符串开始，通过以下两种操作来构建它：

在当前字符串末尾添加任意一个字符。
复制当前整个字符串，并粘贴到末尾（此操作最多只能使用一次）。

求解构建出目标字符串 $S$ 所需的最少操作次数。

思路分析

这是一个典型的动态规划或枚举优化问题。解决问题的关键是决策是否使用以及何时使用那唯一的一次“复制粘贴”操作。我们可以分两种情况来讨论。

设目标字符串 $S$ 的长度为 $n$ 。

情况一：不使用“复制粘贴”操作

如果完全不使用复制操作，那么要得到长度为 $n$ 的字符串 $S$ ，我们必须执行 $n$ 次“添加字符”操作。因此，这种情况下的成本固定为 $n$ 。我们可以将其作为最终答案的一个基准值。

情况二：使用一次“复制粘贴”操作

“复制粘贴”操作的效果是将当前字符串 $P$ 变为 $P \cdot P$ 。这意味着，如果我们决定使用此操作，那么目标字符串 $S$ 的某个前缀必须呈现出 $P \cdot P$ 的结构。

假设我们选择在构建了 $S$ 的前 $i$ 个字符（记为 $P_i$ ）后执行复制操作。要使得这个操作有意义且正确，复制后得到的字符串 $P_i \cdot P_i$ 必须是 $S$ 的一个前缀。这要求 $S$ 的前 $i$ 个字符与紧接着的后 $i$ 个字符完全相同，即 $S[0 \dots i-1] == S[i \dots 2i-1]$ 。

如果这个条件满足，我们来计算总操作数：

构建前缀 $P_i$ : 需要 $i$ 次“添加字符”操作。
复制粘贴: 需要 $1$ 次操作。此时，我们得到了长度为 $2i$ 的前缀 $S[0 \dots 2i-1]$ 。
构建剩余部分: 目标字符串 $S$ 总长为 $n$ ，还剩下 $n - 2i$ 个字符需要添加。这需要 $n - 2i$ 次“添加字符”操作。

因此，对于一个可行的复制点 $i$ ，总操作数为 $i + 1 + (n - 2i) = n - i + 1$ 。

最终策略

我们的目标是找到最小的操作次数。所以，最终答案就是 情况一的成本 与 所有可行的情况二的成本 中的最小值。

算法步骤如下：

初始化最小操作数 min_ops = n。
遍历所有可能的前缀（复制点）长度 $i$ ，范围从 $1$ 到 $\lfloor n/2 \rfloor$ 。
对于每个 $i$ ，判断 $S$ 的前 $i$ 个字符是否等于其后 $i$ 个字符。
如果相等，则计算成本 $n - i + 1$ ，并用它来更新 min_ops：min_ops = min(min_ops, n - i + 1)。
遍历结束后，min_ops 即为最终答案。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    int n = s.length();
    int min_ops = n; // 基准情况：不使用复制操作

    // 遍历所有可能的前缀长度 i
    for (int i = 1; i <= n / 2; ++i) {
        // 检查 S[0...i-1] 是否等于 S[i...2i-1]
        if (s.substr(0, i) == s.substr(i, i)) {
            // 如果可以复制，计算当前操作数
            // i 次添加 + 1 次复制 + (n - 2*i) 次添加
            int current_ops = (i + 1) + (n - 2 * i);
            min_ops = min(min_ops, current_ops);
        }
    }

    cout << min_ops << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        int n = s.length();
        int minOps = n; // 基准情况：不使用复制操作

        // 遍历所有可能的前缀长度 i
        for (int i = 1; i <= n / 2; i++) {
            String prefix = s.substring(0, i);
            String nextPart = s.substring(i, 2 * i);

            if (prefix.equals(nextPart)) {
                // 如果可以复制，计算当前操作数
                // i 次添加 + 1 次复制 + (n - 2*i) 次添加
                int currentOps = (i + 1) + (n - 2 * i);
                minOps = Math.min(minOps, currentOps);
            }
        }

        System.out.println(minOps);
    }
}

def solve():
    s = input()
    n = len(s)
    min_ops = n  # 基准情况：不使用复制操作

    # 遍历所有可能的前缀长度 i
    for i in range(1, n // 2 + 1):
        # 检查 s[0:i] 是否等于 s[i:2*i]
        if s[:i] == s[i:2*i]:
            # 如果可以复制，计算当前操作数
            # i 次添加 + 1 次复制 + (n - 2*i) 次添加
            current_ops = (i + 1) + (n - 2 * i)
            min_ops = min(min_ops, current_ops)
    
    print(min_ops)

solve()

算法及复杂度

算法：枚举
时间复杂度： $O(n^2)$ 。外层循环遍历前缀长度 $i$ ，最多 $n/2$ 次。内层的字符串切片和比较操作，在最坏情况下需要 $O(i)$ 的时间。因此总体复杂度为 $\sum_{i=1}^{n/2} O(i) = O(n^2)$ 。
空间复杂度： $O(n)$ ，用于存储目标字符串以及切片时产生的临时字符串。