[백준] 4354 문자열 제곱 - KMP(JAVA)

문제링크 🚩

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

4354번: 문자열 제곱

 

​

📕 문제 접근 📕

- 굉장히 난처했던 문제 였다.

- 문제 이해가 어려웠는데 정말 간단하게 설명하자면 ababab에서 최대 접미사 접두사의 반복 길이는 abab로 4이다 

- 그치만 해당 문제가 요구하는것은 반복되는 문자열이 몇개의 반복으로 이루어져 있냐는 것이였다.

- 예를 들면 ABCD의 경우 반복되는 것 없기에  ABCD의 1제곱이다. 

- 다음으로 AAAA의 경우 A가 4회 반복되어 해당 문자열을 만들기 때문에 A 의 4제곱이다.

- 다음으로 ABABAB의 경우 AB의 3제곱으로 표현 할 수 있다.

 

- 여기까지 구상하기 어려웠지만 여기까지만 구상했다면 다음은 PI 테이블 혹은 실패함수 등을 통해 어떤식으로 접두사와 접미사의 길이를 통해 문제를 해결 할 수 있다. -> 코드의 주석으로 자세하게 설명하겠다.

 

 

 

💻 Code 💻

package KMP;

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


public class BOJ_4354_문자열제곱 {
    // 문제 의도 파악 S = a ^ N 을 만족하게해야함
    // 말이 굉장히 어렵지만 사실 ababab면 ab의 3제곱으로 이해해야함
    // 테스트 케이스를 1번을 예시로 들면  abcd는 그냥 abcd문자열의 반복임으로 1승을 반환한다
    //  2번의 경우 aaaa 는 a의 4제곱임으로 4를 출력한다
    //  3번의 경우 ababab임으로 ab의 3제곱임으로 3을 출력한다
    private static int makeTable(String str){
        int len = str.length();
        int table[] = new int[str.length()];

        int j = 0;
        int cnt = 0;

        for (int i = 1; i < len; i++) {
            while(j > 0 && str.charAt(i) != str.charAt(j)){
                // 일치하지 않는다면 table 전 값으로 돌림
                // 0 0 1 2 3 0 이였다면 이전 값으로  3으로 다시 가있는거임
                j = table[j -1];
            }
            if(str.charAt(i) == str.charAt(j)){
                table[i] = ++j;
            }
        }
        // 테이블에 접미사와 접두사가 같은 경우를 입력함
        // 3번은 abab 로 4이 나오게 된다.

        // 문자열 전체 길이에서 3을 예시로 들면 ababab에서 접미사와 접두사를 제외하면
        // ab가 남게 되고 이를 전체 길이 6에서 나누면 반복 회수가 나오게 된다.
        // 만약 나머지가 없다면 반복이 없는 것으로 간주하여 1을 반환한다. ex) abcd
        if(len % (len- table[len -1]) != 0){
            return  1;
        }else{
            // ababab => 6 / (6 - 4)  => 3
            // aaaa => aaa가 접미사 접두사로
            // 4 / (4-3) => 4
            return len / (len - table[len -1]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));

        while(true){ // 점이면 멈춰!
            String temp = br.readLine();
            if(temp.equals(".")){
                break;
            }else{
                System.out.println(makeTable(temp));
            }

        }

    }
}