字符串是否由子串拼接

[编程题]字符串是否由子串拼接

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

给出一个非空的字符串，判断这个字符串是否是由它的一个子串进行多次首尾拼接构成的。

例如，"abcabcabc"满足条件，因为它是由"abc"首尾拼接而成的，而"abcab"则不满足条件。

输入描述:

非空字符串

输出描述:

如果字符串满足上述条件，则输出最长的满足条件的的子串；如果不满足条件，则输出false。

示例1

输入

abcabc

输出

abc

算法知识视频讲解

Java

pein531

一个子串要重复，那它起码要重复两次，所以如果存在这样的子串，最长也就是原始串一半的长度。因此从0位置开始截取子串，穷举长度从1~n/2+1的所有子串，看重复之后能否变成原始串。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine().trim();
        int n = str.length();
        String res = "false";
        for(int end = 1; end <= n / 2 + 1; end++){
            int times = n / end;     // 重复次数
            if(times * end == n && str.equals(repeat(str.substring(0, end), times))){
                res = str.substring(0, end);
            }
        }
        System.out.println(res);
    }
    
    private static String repeat(String s, int times) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < times; i++){
            sb.append(s);
        }
        return sb.toString();
    }
}

发表于 2022-01-18 12:37:43 回复(0)

Java

雨果伽利略

使用HashSet的方法；

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str=scanner.nextLine();
if(str==null||str.equals("")){
System.out.println(false);
}
        Set<Character> set=new LinkedHashSet<>();

        for (int i = 0; i < str.length(); i++) {
            set.add(str.charAt(i));
        }
        int length = str.length();

        if(length%set.size()==0){
            for (Character c : set) {
                System.out.print(c);
            }
        }else{
            System.out.println(false);
        }

}
}

发表于 2019-03-04 10:01:05 回复(1)