백준 : 4354 java

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

4354번: 문자열 제곱

 

KMP 알고리즘의 Pi값을 이용해서 문제를 풀수 있었다.

 

ababab 문자열의 Pi값을 구해보면 = [0, 0, 1, 2, 3, 4] 라는걸 알 수 있다.

 

여기서 Pi값은 무엇을 나타내는 것일지 생각해본다면 Pi[x] = y 라 할때

 

0~y 의 배열들이  (length - y) ~ x 까지 패턴과 똑같다라는 것을 나타낸다.

 

0~ y : abab

(length - y) ~ x : abab

 

여기서 구해야할 것은 가장 작은 단위의 반복이다. 즉 abㅣabㅣab  라면 length - Pi[x] 값이 2가되고 이것이 가장 작은 반복 단위가된다. 

 

그러면 length / 반복단위 하면 되는 것일까??? 문제가있다. 길이가 7인것에도 반복단위가 2일 수도있다.

ex) abababa   -> 반복 단위 2   하지만 답은 1이다. 따라서 반복단위로 나누어 떨어지지 않으면 1을 출력한다.

 

package algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class B4354 {
 
    public static int[] getPi(String Pattern) {
        int[] Pi = new int[Pattern.length()];
 
        int j = 0;
 
        for (int i = 1; i < Pattern.length(); i++) {
 
            while (j > 0 && Pattern.charAt(i) != Pattern.charAt(j)) {
                j = Pi[j - 1];
            }
 
            if (Pattern.charAt(i) == Pattern.charAt(j)) {
                Pi[i] = ++j;
            }
        }
        return Pi;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            String Pattern = br.readLine();
            if (Pattern.charAt(0) == '.')
                break;
            int[] Pi = getPi(Pattern);
            int ans = Pi.length % (Pi.length - Pi[Pi.length - 1]) == 0 ? Pi.length / (Pi.length - Pi[Pi.length - 1])
                    : 1;
 
            sb.append(ans).append('\n');
        }
 
        System.out.print(sb.toString());
    }
}