[백준][Java] 16916번 부분 문자열 (문자열, KMP)

KMP알고리즘을 이해는 하되, 이 밑에 있는거 통째로 구현할 필요 없음

걍 라인마다 뭔 소리하는지 충분히 이해만 하면 됨

이걸 처음부터 끝까지 구현하는 것은 알고리즘을 잘하는 사람이 아니라 차력쇼를 잘하는거임

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    static List<Integer> li;
    static int count;
    
    private 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) {
                    count = 1;
                    return;
                }
                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;
    }
    
    public static void main(String[] args) throws IOException{
        String origin = br.readLine();
        String pattern = br.readLine();
        
        li = new ArrayList<>();
        KMP(origin, pattern);
        System.out.println(count);
        
//        bw.write("");
//        bw.flush();
//        bw.close();
        
            
        
    }
    
//    private static int stoi(String input) {
//        return Integer.parseInt(input);
//    }
    
}