[백준 알고리즘] 백준 16916번 - 부분 문자열(JAVA)

문제

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

16916번: 부분 문자열

 

문제풀이

 

1) 실패코드 - contains 함수를 이용하여 S에 P가 포함되는지 안되는지 판별 후 포함되면 1, 포함되지 않으면 0을 출력 => 시간초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
 
public class Main_BOJ_16916_부분문자열2 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String S = br.readLine();
        String P = br.readLine();
        
        if(S.contains(P)) System.out.println(1);
        else System.out.println(0);
                
    }
 
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class KMP {
    public static int result, pi[];
    public static String origin, pattern;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        origin = br.readLine();
        pattern = br.readLine();
        
        pi = new int[pattern.length()];
        getPi();
        KMP();
    }
 
    private static void getPi() {
        int j=0;
        for (int i = 1; i < pattern.length(); i++) {
            //일치하는 위치가 나올 떄까지 j-1칸의 공통 부분 위치로 이동
            while(j>0 && pattern.charAt(i) != pattern.charAt(j)) {
                j=pi[j-1];
            }
            //일치하는 경우
            if(pattern.charAt(i) == pattern.charAt(j)) {
                //i길이 문자열의 공통 길이는 j의 위치 +1
                pi[i]=++j;
            }
        }
        
    }
 
    private static void KMP() {
        int j=0;
        for (int i = 0; i < origin.length(); i++) {
            //일치하는 위치가 나올 때까지 j-1칸의 공통 부분 위치로 이동
            while(j>0 && origin.charAt(i) != pattern.charAt(j)) {
                j = pi[j-1];
            }
            //일치하는 경우
            if(origin.charAt(i) == pattern.charAt(j)) {
                if(j== pattern.length()-1) {
                    result=1;
                    break;
                }
                //맞았지만 패턴이 끝나지 않았다면 j를 증가
                else ++j;
            }
        }
        System.out.println(result);
    }
}