[ BOJ ][JAVA][16916] 부분 문자열

www.acmicpc.net/problem/16916

16916번: 부분 문자열

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	3873	1233	898	38.574%

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

예제 입력 1

baekjoon
aek

예제 출력 1

1

예제 입력 2

baekjoon
bak

예제 출력 2

0

예제 입력 3

baekjoon
joo

예제 출력 3

1

예제 입력 4

baekjoon
oone

예제 출력 4

0

예제 입력 5

baekjoon
online

예제 출력 5

0

예제 입력 6

baekjoon
baekjoon

예제 출력 6

1

코드

import java.util.*;
import java.io.*;

public class p16916 {
    static String origin;
    static String pattern;
    static int cnt = 0;
    static List<Integer> li;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        origin = br.readLine();
        pattern = br.readLine();
        li = new ArrayList<>();
        KMP(origin, pattern);
        if (cnt > 0) {
            System.out.println("1");
        } else {
            System.out.println("0");
        }

    }

    static void KMP(String org, String ptn) {
        int pi[] = getPi(ptn);
        int j = 0;
        for(int i=0; i<org.length(); i++) {
            while(j>0 && org.charAt(i)!=ptn.charAt(j)) {
                j = pi[j-1];
            }
            if(org.charAt(i)==ptn.charAt(j)) {
                if(j==ptn.length()-1) {
                    ++cnt;
                    li.add(i-j+1);
                    j=pi[j];
                } else {
                    j++;
                }
            }
        }
    }

    static int[] getPi(String ptn) {
        int[] pi = new int[ptn.length()];
        int j = 0;
        for(int i=1; i<ptn.length(); i++){
            while(j>0 && ptn.charAt(i)!=ptn.charAt(j)){
                j = pi[j-1];
            }
            if(ptn.charAt(i) == ptn.charAt(j))
                pi[i] = ++j;
        }
        return pi;
    }
}