백준 찾기

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다.
T와 P의 길이 n, m은 1이상 100만 이하이고, 알파벳 대소문자와 공백으로만 이루어져 있다.

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다.
둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다.
예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다.

내가 이 문제를 보고 생각해본 부분

makePi 함수는 패턴 P의 pi 배열을 만든다.
pi 배열은 현재 위치까지 접두사이자 접미사인 최대 길이를 저장한다.
예를 들어, ABAB이라면 pi 배열은 [0,0,1,2]가 된다.
kmp 함수는 텍스트 T와 패턴 P, 그리고 pi 배열을 받아서 T에서 P가 나타나는 모든 시작 위치를 찾아낸다.
i는 T의 인덱스이고, j는 P의 인덱스이다.
문자 비교가 안 맞으면 pi 배열을 참고해 패턴 인덱스를 조정해 준다.
매칭 성공 시 시작 위치를 저장하고, j를 다시 pi 값만큼 이동해 다음 매칭 준비를 한다.
실행 후 결과는
첫 줄: 매칭된 횟수
둘째 줄: 매칭 시작 위치들을 공백으로 구분해 출력한다.

코드로 구현

package baekjoon.baekjoon_33;

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

// 백준 1786번 문제
public class Main1324 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String T = br.readLine();
        String P = br.readLine();

        int[] pi = makePi(P);
        ArrayList<Integer> result = kmp(T, P, pi);

        System.out.println(result.size());
        for (int pos : result) {
            System.out.print(pos + " ");
        }

        br.close();
    }

    // KMP 전처리: pi 배열 생성
    static int[] makePi(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];
        int j = 0;

        for (int i = 1; i < m; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
                pi[i] = j;
            }
        }
        return pi;
    }

    // KMP 검색: T에서 P가 나타나는 모든 위치 리턴 (1-based index)
    static ArrayList<Integer> kmp(String text, String pattern, int[] pi) {
        ArrayList<Integer> result = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        int j = 0;

        for (int i = 0; i < n; i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                if (j == m - 1) {
                    // 매칭 성공 위치 저장 (1-based)
                    result.add(i - m + 2);
                    j = pi[j];
                } else {
                    j++;
                }
            }
        }
        return result;
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.