찾기

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

풀이

KMP 알고리즘을 이용해서 풀어야하는 문제이다.

가장 쉽게 생각할 수 있는 방법은 브루트포스 방법으로 한글자씩 비교해가면서 틀린 문자가 나오면 한칸 이동해서 처음부터 다시 비교하는 방법이다. 하지만 이 방법은 시간복잡도가 n*m이라서 문자열이 길수록 시간이 오래걸린다.

그래서 나온 방법이 KMP 알고리즘으로 시간복잡도가 n+m이다.

KMP 알고리즘에 대해 완벽하게 이해를 하지 못해 자세히 설명을 적지 못하고 구글을 참고해서 다시 복습해야할 것 같다.

코드

import java.beans.PropertyEditorSupport;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int n, m;
    static int[] pi;
    static int result = 0;
    static ArrayList<Integer> idx;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String t = br.readLine();
        String p = br.readLine();

        pi = new int[p.length()];
        idx = new ArrayList<>();
        makePi(p);
        // bw.write(Arrays.toString(pi)+"\n");
        KMP(t,p);
        bw.write(result+"\n");
        for(int a : idx)
            bw.write(a+" ");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void makePi(String p) {
        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;
        }
    }

    private static void KMP(String t, String p) {
        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){
                    result++;
                    idx.add(i - p.length() + 2);
                    // 검사에서 통과했다면 접두어는 통과했기때문에 접두어 이후 검사를 위해 j를 변경
                    j = pi[j];
                }
                else
                    ++j;
            }
        }
    }
}