[백준] 1786. 찾기

문제 링크

[백준] 1786. 찾기

풀이 과정

KMP 알고리즘이 적용된 기본 문제입니다.

KMP 알고리즘에 대한 설명은 링크에 있습니다.

T : ABC ABCDAB ABCDABCDABDE
P : ABCDABD

KMP 알고리즘에 따라 i와 j의 인덱스가 위와 같을 때 패턴 매칭이 성공한 것을 알 수 있습니다. 이 때 i - P.length() + 2 인 16이 문제에서 원하는 P가 나타나는 시작 위치가 됩니다.

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static String T, P;
    static int cnt;
    static List<Integer> idxList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        T = sc.nextLine();
        P = sc.nextLine();

        KMP();

        System.out.println(cnt);
        for (int idx : idxList)
            System.out.print(idx + " ");
    }

    public static int[] getPi() {
        int[] pi = new int[P.length()];

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

            if (P.charAt(i) == P.charAt(j))
                pi[i] = ++j;
        }

        return pi;
    }

    public static void KMP() {
        int[] pi = getPi();

        int j = 0;
        for (int i = 0; i < T.length(); i++) {
            while (j > 0 && T.charAt(i) != P.charAt(j)) {
                j = pi[j - 1];
            }

            if (T.charAt(i) == P.charAt(j)) {
                if (j == P.length() - 1) {
                    cnt++;
                    idxList.add(i - P.length() + 2);

                    j = pi[j];
                } else {
                    j++;
                }
            }
        }
    }
}