찾기 - KMP 알고리즘

<참고>

www.youtube.com/watch?v=UcjK_k5PLHI

m.blog.naver.com/PostView.nhn?blogId=rokey_89&logNo=221497982117&proxyReferer=https:%2F%2Fwww.google.com%2F

백준 1786 : 찾기 (JAVA) KMP알고리즘

www.acmicpc.net/problem/1786

1786번: 찾기

package String;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

// 백준 찾기
public class Find {


    public static int[] getPi(String pattern){ //패턴 찾기
        int len = pattern.length();
        int []pi = new int[len];
        int j=0;
        for(int i=1; i<len; i++){
            while(j>0 && pattern.charAt(i)!= pattern.charAt(j)){
                j = pi[j-1];
            }
            if(pattern.charAt(i)==pattern.charAt(j)){
                pi[i]=++j;
            }
        }

        return pi;
    }

    public static ArrayList<Integer>KMP(String str, String pattern){
        ArrayList<Integer> list = new ArrayList<>();
        int [] pi = getPi(pattern);
        int len = str.length();
        int plen = pattern.length();
        int j =0;

        for(int i=0; i<len; i++){
            while(j>0 && str.charAt(i)!=pattern.charAt(j)) {
                j = pi[j - 1];
            }
            if(str.charAt(i)==pattern.charAt(j)){
                if(j==plen-1){
                    list.add(i-plen+1);
                    j = pi[j];
                }else{
                    j++;
                }
            }
        }
        return list;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String target = br.readLine();
        String tofind = br.readLine();

        ArrayList<Integer> list = KMP(target, tofind);  //KMP 함수의 반환값 저장
        int size = list.size();                          // 찾은 패턴이 몇개인지 저장할 변수
        System.out.println(size);                        // 찾은 패턴의 개수 출력

        for(int i=0; i<size; i++) {                      // List의 size만큼 해당 인덱스를 출력한다
            System.out.print(list.get(i)+1+" ");
        }


    }

}