[백준] 11585. 속타는 저녁 메뉴(Java)

문제

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

주어진 문자열 T, P에서 T 문자열 내에 P가 몇 번 나타내는지 출력하는 문제입니다.

주어진 문자 T는 원형입니다.

'몇 번 나타내는지 / 문자열에서 발생할 수 있는 경우의 수'를 기약분수로 출력합니다.

 

 

풀이

접두사 기준으로 일치하는 부분 문자열 찾는 알고리즘인 KMP를 활용해서 해결했습니다.

이때 원형으로 이루어진 T 문자열을 체크하기 위해, T+T 문자열을 바탕으로 P와 비교했습니다.

 

1. 문자열 P(pattern)를 이용해서 테이블을 형성하고
2. 만들어진 테이블과 문자열 T와 P를 이용해서 비교를 진행합니다.
3. 비교를 마친 후, 기약 분수로 결과 값을 출력하기 위해 GCD를 구합니다.

4. 값을 출력합니다.

 

코드

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

public class Main {
    static int N;
    static int[] table;
    static StringTokenizer st;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        String T = makeString(br.readLine());
        String P = makeString(br.readLine());

        makeTable(P);

        int res = KMP(T+T, P);

        int gcd = getGCD(N, res);

        System.out.print((res/gcd) + "/" + (N/gcd));
    }

    static void makeTable(String P) {
        // 테이블 생성
        table = new int[N];

        int idx = 0;

        // 접두사를 기준으로, kmp 알고리즘 진행
        for (int i = 1; i < N; i ++) {
            while (idx > 0 && P.charAt(i) != P.charAt(idx))
                idx = table[idx - 1];

            if (P.charAt(i) == P.charAt(idx)) {
                // 부분 문자열 길이 1 증가
                idx += 1;
                table[i] = idx;
            }
        }
    }

    private static int KMP(String T, String P) {
        int len = T.length();
        int cnt = 0;
        int idx = 0;

        for(int i = 1 ; i < len ; i ++){
            while(idx > 0 && T.charAt(i) != P.charAt(idx))
                idx = table[idx-1];

            // P와 동일한 값이 T에 있다면
            if(T.charAt(i) == P.charAt(idx)){
                if(idx == N - 1){
                    cnt ++;
                    idx = table[idx];
                }
                else idx += 1;
            }
        }

        return cnt;
    }

    private static int getGCD(int a, int b) {
        int r;
        while(b > 0){
            r = a % b;
            a = b;
            b = r;
        }

        return a;
    }

    static String makeString(String s){
        sb = new StringBuilder();
        st = new StringTokenizer(s);

        for(int i = 0 ; i < N ; i ++)
            sb.append(st.nextToken());

        return sb.toString();
    }
}