[백준 1786] 찾기 - JAVA

BOJ Link

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

 

풀이 과정

스탠다드한 KMP 문제이다.  문제 또한 KMP의 기본 개념을 그대로 설명하고 있다.

 

헤맨 부분

반례 하나를 고려하지 못해서 오답이 있었다.

 

input :

ABABA

ABA

 

answer :

2

1 3

 

wrong answer :

1

1

 

해당 문자열에서 ABA라는 문자열은 idx 0~2에 위치한다.

탐색 이후 idx 3번부터 재탐색을 하게 되면, idx 2~4에 위치한 케이스를 고려하지 못한다.

 

이후 수정하여 정답을 받았다.

 

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String parent = br.readLine();
        String pattern = br.readLine();

        int n = parent.length();
        int m = pattern.length();

        int[] table = new int[m];

        int j = 0;
        for (int i = 1; i < m; i++) {

            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = table[j - 1];
            }

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

        j = 0;
        int matchCnt = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            while (j > 0 && parent.charAt(i) != pattern.charAt(j)) {
                j = table[j - 1];
            }

            if (parent.charAt(i) == pattern.charAt(j)) {
                j++;

                // j는 0 ~ m-1까지 비교한다.
                if (j == m) {
                    matchCnt++;
                    // 문제에서 idx=0은 1번째 문자이므로 +1
                    sb.append(i - (j - 1) + 1).append(" ");
                    j = table[j - 1];
                }
            }
        }

        System.out.println(matchCnt);
        System.out.println(sb);
    }
}