[백준] 1786 찾기 - Java

 

 

 

문제가 제발 kmp알고리즘으로 풀어달라고 한다..

 

kmp알고리즘은 접두사와 접미사가 최대로 같을 수 있는 길이를 찾고... 이 길이를 바탕으로 완전탐색으로 해결할 문제를 훨씬 빠르게 해결할 수 있게 하는 알고리즘인데.. 구현이 까다롭진 않아서 몇 번 해보면 외워진다.

 

모르면 틀려야되지만 알면 쉽게 풀 수 있는 문제다. 

 

 

 

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

public class Main {

    static ArrayList<Integer> list;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine();
        String target = br.readLine();

        list = new ArrayList<>();

        int[] pi = new int[target.length()];

        int j = 0;

        for(int i=1; i<target.length(); i++){
            while(j > 0 && target.charAt(j) != target.charAt(i)){
                j = pi[j-1];
            }

            if(target.charAt(j) == target.charAt(i)){
                j++;
                pi[i] = j;
            }
        }

//        for(int k : pi){
//            System.out.print(k + " ");
//        }


        j = 0;
        int str_len = str.length();
        int target_len = target.length();

        for(int i=0; i<str_len; i++){
            while(j > 0 && str.charAt(i) != target.charAt(j)){
                j = pi[j-1];
            }

            if(str.charAt(i) == target.charAt(j)){
                if(j + 1 == target_len){
                    list.add(i - target_len + 2);
                    j = pi[j];
                }else{
                    j++;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int k : list){
            sb.append(k + " ");
        }

        System.out.println(list.size());
        System.out.println(sb);

        

    }
}