[Platinum V] 문자열 제곱 - 4354

문제 링크

성능 요약

메모리: 97008 KB, 시간: 460 ms

분류

KMP, 문자열

제출 일자

2024년 8월 28일 04:10:34

문제 설명

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

• a^0 = "" (빈 문자열)
• a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

입력

입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다.

출력

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

문제 풀이

KMP알고리즘 문제다. KMP로 마지막까지 반복되는 접두사 길이 체크하고 그 길이만큼 전체 문자열이 딱 떨어진다면 같은 패턴으로 쭉 반복되기에 지수곱 사용가능하므로 문자열길이 / 패턴길이로 답 구하면된다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static String T;
	static int L, pi[], maxExp;

	public static void main(String[] args) throws IOException {
//        br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        
		while (true) {
            T = br.readLine();
            if (T.equals(".")) break;
            
            maxExp = getMaxExponent();
            bw.write(maxExp + "\n");
        }
		bw.flush();
        bw.close();
        br.close();
	}

	private static int getMaxExponent() {
		int[] pi = new int[T.length()];
		int j=0; 
		int maxExponent = 0;
		
		for(int i=1; i<T.length(); i++) {
			while(j>0 && T.charAt(i) != T.charAt(j)) j = pi[j-1];
			
			if(T.charAt(i) == T.charAt(j)) pi[i] = ++j;
		}
//		System.out.println(Arrays.toString(pi));
		
        int repeatLen = T.length()-pi[T.length()-1];
        return maxExponent = T.length()%repeatLen==0 ? T.length()/repeatLen : 1;

		
	}
}