백준 1786: 찾기 [플래티넘 Ⅴ / JAVA]

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

1786번: 찾기

---

 

• 알고리즘 : KMP
• 풀이 날짜 : 2023.07.12.

 

 

< 풀이 설명 >

해당 문제는 KMP에 추가적인 구현만 하면 된다.

 

 

 

KMP 에 대한 설명은 다음과 같다.

 

[백준/플래티넘] - 백준 11585: 속타는 저녁 메뉴 [플래티넘 Ⅴ / JAVA]

 

 

 

< 코드 >

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

public class Main {

    static int[] table;
    static String text, ptr;
    static StringBuilder sb = new StringBuilder();

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


        int len = ptr.length();
        table = new int[len];
        setTable();


        System.out.println(kmp(len));
        System.out.println(sb);
    }

    public static void setTable() {
        int i = 0;

        // i: 움직(앞), j: 뒤
        for (int j = 1; j < ptr.length(); j++) {
            while (i > 0 && ptr.charAt(j) != ptr.charAt(i))
                i = table[i - 1];

            if (ptr.charAt(j) == ptr.charAt(i))
                table[j] = ++i;
        }

    }

    public static int kmp(int len) {
        int count = 0;
        int j = 0;

        for (int i = 0; i < text.length(); i++) {
            while (j > 0 && text.charAt(i) != ptr.charAt(j))
                j = table[j - 1];

            if (text.charAt(i) == ptr.charAt(j)) {
                if (j == ptr.length() - 1) {
                    sb.append(i + 2 - len).append(" ");
                    count++;
                    j = table[j];
                } else j++;
            }
        }

        return count;
    }

}