[백준] 1786. 찾기(Java)

문제

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

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

 

풀이

접두사 기준으로 일치하는 부분 문자열 찾는 알고리즘인 KMP를 활용해서 해결했습니다.
이때 문자열 P(pattern)를 이용해서 테이블을 형성하고
만들어진 테이블과 문자열 T와 P를 이용해서 비교를 진행합니다.

1) T.charAt(i) == P.charAt(idx)가 true일 때
idx == pLen - 1가 true라면 T 문자열 내에 P가 존재한다는 뜻이므로
카운트를 증가시켜줍니다.(P값이 T의 몇번째 인덱스에서 만들어졌는지 알기위해 list에 i-idx+1 값을 추가해줍니다.)
2) 1)의 케이스에 해당하지 않는다면 idx를 ++ 합니다.

비교를 마친 후
T 문자열 내에 P가 몇 번 나타내는지 출력하기 위해 list.size()를 출력하고
list 내에 저장된 값(몇번째 인덱스에서 동일한 값이 만들어졌는지)을 출력합니다.

 

코드

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

public class Main {
    static String T, P;
    static int tLen, pLen;
    static int[] table;
    static List<Integer> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        tLen = T.length();
        pLen = P.length();

        // 정답이 담길 리스트(T 내에 P가 있다면 몇번째 인덱스에서 시작되는지 저장)
        list = new ArrayList<>();

        makeTable();

        comparison();

        sb.append(list.size()).append("\n");

        for(int res: list)
            sb.append(res).append("\n");

        System.out.print(sb);
    }

    private static void comparison() {
        int idx = 0;

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

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

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

        // kmp 진행에 필요한 인덱스
        int idx = 0;

        // 접두사를 기준으로, kmp 알고리즘 진행
        for(int i = 1 ; i < pLen ; 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;
            }
        }
    }
}