백준 16916 - 부분 문자열 (자바)

문제

풀이

import java.util.Scanner;

public class Main {
    private static int[] buildPi(String p) {
        int m = p.length();
        int[] pi = new int[m];
        int j = 0;

        for(int i=1; i<m; 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;
    }

    private static boolean kmp(String s, String p) {
        int n = s.length();
        int m = p.length();
        int[] pi = buildPi(p);
        int j=0;

        for(int i=0; i<n; i++) {
            while(j>0 && s.charAt(i) != p.charAt(j)) {
                j= pi[j-1];
            }
            if(s.charAt(i) == p.charAt(j)) {
                if(j == m-1) {
                    return true;
                } else {
                    j++;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        String P = sc.next();
        sc.close();
        boolean found = kmp(S,P);
        System.out.print(found ? 1 : 0);
    }
}

contains를 사용하여 풀이하였더니 시간초과가 발생
kmp 알고리즘을 이용하여 풀이