[BOJ] 백준 4354 문자열 제곱

출처:  https://www.acmicpc.net/problem/4354

 Input 

abcd

aaaa

ababab

.

 

 Output 

1

4

3

 

▶ (abcd)1  /  (a)4  /  (ab)3

 

 

주어진 문자열에서 최대한 짧은 부분 문자열을 거듭 이용해서 전체 문자열을 만들어야 합니다.

ex) "abababab"는 "ab"를 4번 반복하면 만들 수 있습니다.

 

KMP알고리즘에서 실패 함수 테이블의 맨 마지막 값을 구합니다. 

실패함수가 반복되는 패턴(Pattern)을 찾아내는 것이기 때문입니다.

ex) S = "ababab"의 실패 함수 마지막 값은 pi[S.length() - 1] = 4 입니다.

      여기서, S.length() - pi[S.length() - 1] = 6 - 4 = 2 입니다. ← 반복되는 문자열 크기

      최종적으로 S.length() / (반복되는 문자열 크기) = 6 / 2 = 3 ← 답

 

 

"abcabcab", "abababa", "ababa" 등과 같이 문자열 제곱수로 표현할 수 없지만,

접두사와 접미사가 모두 될 수 있는 부분문자열이 있는 경우 

실패 함수 마지막 값 pi[S.length() - 1]  > 1 임에도 반복되는 문자열로 나눠지지 않는 Case가 있습니다.

---

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            String S = br.readLine();
            if (S.equals(".")) return;
             
            // KMP 알고리즘 실패함수 테이블
            int[] pi = makeTable(S);
             
            // 실패함수의 마지막 원소 값
            int piVal = pi[S.length() - 1];
             
            // 반복되는 횟수(거듭제곱 크기)
            if(S.length() % (S.length() - piVal) != 0)
                System.out.println(1);
            else
                System.out.println(S.length() / (S.length() - piVal));
        }
    }
 
    private static int[] makeTable(String patternStr) {
        // 테이블 배열 생성
        char[] pattern = patternStr.toCharArray();
        int pLen = pattern.length;
        int[] table = new int[pLen];
         
        int j = 0;
        for(int i=1; i<pLen; i++) {
            while(j>0 && pattern[i] != pattern[j]) {
                j = table[j-1];
            }
            if(pattern[i] == pattern[j]) {
                table[i] = ++j;
            }
        }
        return table;
    }
     
}