[백준] 1786 찾기 -KMP(JAVA)

문제링크 🚩

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

1786번: 찾기

 

 

​

📕 문제 접근 📕

- 가장 이상적인 KMP문제인 것 같다

- 접미사와 접두사가 같은 영역을 찾기 위한 table을 만들고 

- 이를 KMP 알고리즘에 대입하여 해결하면 되는 문제다 

- KMP 알고리즘은 해당 포스팅에 자세하게 정리해뒀으니 참고 바란다.

https://security-gom.tistory.com/36

KMP -JAVA

 

💻 Code 💻

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

public class BOJ_1786_찾기 {
    public static int[] makeTable(String p){
        int plen = p.length();
        int[] table = new int[plen];

        int j = 0;

        for (int i = 1; i < plen; i++) {
            // a b a c
            while(j > 0 && p.charAt(i) != p.charAt(j)){
                // 문자열 매칭 시작
                // 연속 일치 하지 않으면 j 값을 돌려주어 다시 매칭 시작
                j = table[j -1];
            }
            if(p.charAt(i) == p.charAt(j)){
                table[i] = ++j;
            }
        }
        return table;
    }

    public static void KMP(String str, String pattern) {
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        int[] table = makeTable(pattern);
        int sLen = str.length();
        int pLen = pattern.length();

        int idx = 0; // 현재 대응되는 글자 수
        for (int i = 0; i < sLen; i++) {
            // idx번째 글자와 짚더미의 해당 글자가 불일치할 경우
            // 현재 대응된 글자의 수를 table[idx - 1]번으로 줄임
            while (idx > 0 && str.charAt(i) != pattern.charAt(idx)) {
                idx = table[idx - 1];
            }
            // 글자가 대응될 경우
            if (str.charAt(i) == pattern.charAt(idx)) {
                if (idx == pLen - 1) {
                    cnt++;
                    // parent 문자열과 pattern 문자열이 일치하기 시작한 시점을 출력
                    sb.append(i - idx + 1 + "\n");
                    idx = table[idx];
                }
                else {
                    idx++;
                }
            }
        }
        System.out.println(cnt);
        System.out.println(sb.toString());
    }

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

        KMP(s1, s2);
    }
}

 

 

 

📖 회고 📖

- KMP  를 처음 학습하고 적용하기에 가장 적합한 문제 인 것 같다 .