小红的字符串

[编程题]小红的字符串

热度指数：255 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红一开始有一个空串，每次操作可以在这个串的末尾添加任意一个字符，另外最多有一次操作，可以复制当前字符串本身，然后粘贴到末尾。现在小红想知道，最少经过多少次操作，可以得到目标字符串。

输入描述:

第一行一个字符串 ，表示目标字符串，长度不超过 1000。

输出描述:

输出一个整数，表示最少操作次数。

示例1

输入

ababababc

输出

说明

先执行四次添加操作，得到 abab，然后复制粘贴一次，得到 abababab，最后添加一次 c。

算法知识视频讲解

Python

virceus

s = input()
n = len(s)
min_ops = n # 直接添加
 
fori in range(1,n//2+1): 
    if s[:i] == s[i:2*i]: # 结构重复
        min_ops = min(n - i + 1, min_ops) # 少 i 次添加操作, +1 次复制操作
    # print(s[:i], min_ops)
print(min_ops)

编辑于 2025-09-21 02:01:36 回复(0)

Java

333lll

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        StringBuilder sb = new StringBuilder();
        int max = 0;
        for (int i = 0, j = 0; i < s.length() ; i++) {
            sb.append(s.charAt(i));
            int idnex = s.lastIndexOf(sb.toString());
            if (idnex != -1 && idnex > i) {
                max = Math.max(max, sb.toString().length());
            } else {
                //sb = new StringBuilder();
                int cnt = 0;
                while (j < i) {
                    sb.setCharAt(cnt, '\0');
                    int id = s.lastIndexOf(sb.toString());
                    if (id != -1 && id > i) {
                        break;
                    }
                    j++;
                    cnt++;
                }
            }
        }

        //System.out.println(max);

        System.out.println(s.length() + 1 - max);
    }
}

发表于 2025-06-29 20:34:55 回复(0)