455 - Periodic Strings

🌕🌗🌑🌑🌑

# 題目連結

• 題目連結
• Online Judge
• uDebug

# 題目說明

Time limit: 3.000 seconds

# 題目

A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k . For example, the string ”abcabcabcabc” has period 3 , since it is formed by 4 repetitions of the string ”abc” . It also has periods 6 (two repetitions of ”abcabc” ) and 12 (one repetition of ”abcabcabcabc” ).

Write a program to read a character string and determine its smallest period.

# Input

The first line oif the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line. Each test case will contain a single character string of up to 80 non-blank characters. Two consecutive input will separated by a blank line.

# Output

An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line.

# Sample Input

1

HoHoHo

# Sample Output

2

# 解題技巧

暴力解，利用擷取 substring 然後再重新組裝 time = inputstring.length() / substring.length() 次，當 inputstring 與重新組裝的字串相同就表示 substring 為 inputstring 重複的字串，而 substring.length() 及為答案。

# Solution

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        for (int i = 0; i < N; i++) {

            String str = sc.next();

            if (i != 0)

                System.out.println();

            int len = str.length();

            for (int j = 0; j < len; j++) {

                int subLen = j + 1;

                if(len % subLen != 0)

                    continue;

                String subStr = str.substring(0, subLen);

                int time = len / subLen;

                String compare = "";

                for(int k = 0; k < time; k++){

                    compare += subStr;

                }

                if(compare.equals(str)){

                    System.out.println(subLen);

                    break;

                }

            }

        }

        sc.close();

    }

}