[백준] 16916. 부분 문자열

brute force로 풀려고하면 문자열의 길이가 최대 100만-1이고, O(NM)으로 시간초과가 발생한다.

접두사와 접미사로 이미 검사한 부분을 건너뛰는 아이디어를 활용한 KMP 알고리즘을 활용하면 O(N+M)으로 풀 수 있다.

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));
        char[] s = br.readLine().toCharArray();
        char[] p = br.readLine().toCharArray();
        int slen = s.length;
        int plen = p.length;
        int[] table = new int[p.length];
        int k = 0;

        for (int i = 1; i < plen; i++) {
            while (k > 0 && p[i] != p[k]) {
                k = table[k - 1];
            }
            if (p[i] == p[k]) {
                table[i] = ++k;
            }
        }

        k = 0;
        for (int i = 0; i < slen; i++) {
            while (k > 0 && s[i] != p[k]) {
                k = table[k - 1];
            }
            if (s[i] == p[k]) {
                if (k == plen - 1) {
                    k = table[k];
                    System.out.println(1);
                    return;
                }
                k++;
            }
        }

        System.out.println(0);
        br.close();
    }
}