[SWEA] 4040 문자열의 거듭제곱

출처: [SWEA] SW 문제해결 심화 - 문자열 알고리즘

 Input 

3

abcd

aaaa

ababab

 

 Output 

#1 1

#2 4

#3 3

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

 

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

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

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

※ [BOJ] 4354 문자열 제곱 

[BOJ] 백준 4354 문자열 제곱

---

import java.io.*;
 
public class Solution {
     public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new  InputStreamReader(System.in));
 
           int T = Integer.parseInt(br.readLine());
           for (int tc = 1; tc <= T; tc++) {
                String S = br.readLine();
                 
                // KMP 알고리즘 실패함수 테이블
                int[] pi = makeTable(S);
                 
                System.out.print("#" + tc + " ");
                System.out.println(pi[S.length() - 1]);
                if(S.length() % (S.length() - pi[S.length() - 1]) != 0)
                    System.out.println(1);
                else
                    System.out.println(S.length() / (S.length() - pi[S.length() - 1]));
           }
     }
      
    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;
    }
}