[백준][Java] 1786번 찾기 (문자열, KMP)

210930

Line : j = 0으로 해서 틀렸음 이거 j = pi[j]로 시작해야함 진짜 기존에 돌았던 부분

뼛속 사골까지 우려서 써먹어야 통과 가능한 문제임

솔직히 혼자서 짤만함 getPi와 KMP가 진짜 비슷하게 생겼음

getPi를 완전히 꿰서 이해하면 KMP까지 이해하는 것이 한층 수월함

 

 

 

 

KMP알고리즘도 처음 알았고 봐도 풀기 좀 힘든 것 같음

 

Line:23~25 부분은 좀 더 공부가 필요하고

Line:30은 솔직히 봐도 모르겠음 

 

단어 탐색 알고리즘 중에 KMP알고리즘이 있고 이것을 이용하여

O(N*M) -> O(N+M)으로 시간을 단축시켜줄 수 있다 이정도로만 이해하면 될듯

솔직히 이거 알고리즘 구현하는 짓거리는 좀 오바같음

 

시간 단축 sysout -> StringBuilder

 

 

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;
                    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;
    }
    
    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);
        StringBuilder sBuilder = new StringBuilder();
        for (int i : li) {
            sBuilder.append(i+" ");
        }
        System.out.println(sBuilder.toString());
        
//        bw.write("");
//        bw.flush();
//        bw.close();
        
            
        
    }
    
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
    
}