[BOJ] 1786. 찾기

이문제는 문자열 패턴찾기 문제이다.

단순히 일반적으로 찾으면 시간초과가 생겨서 풀수 없는 문제이다. 그렇기에 대표적인 문자열 알고리즘의 대표적인 KMP를 사용하였다. KMP의 알고리즘의 간단한 원리는 일단 패턴문자열에 대해 해당 문자열의 위치마다에서 접두사와 접미사가 최대로 같아지는 것을 카운팅해주는 배열을 만든다음, 그 배열을 이용하여 접두사와 접미사를 확인해가며 일정간격을 건너뛰어 시간복잡도가 거의 O(n)에 가깝도록 해결하는 방식이다.

package study5;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
public class Main_bj_1786_찾기 {
    static int count;
    static List<Integer> list;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine();
        String pattern=br.readLine();
        
        count=0;
        list=new ArrayList<>();
        kmp(str,pattern);
        System.out.println(count);
        for(int num : list) {
            System.out.println(num);
        }
    }
    
    
    static void kmp(String str, String pattern) {
        int[] p = find(pattern);
//        System.out.println(Arrays.toString(p));
        int j=0;
        
        for(int i=0;i<str.length();i++) {
            while(j>0 && str.charAt(i)!=pattern.charAt(j)) {
                j=p[j-1];
            }
            
            if(str.charAt(i)==pattern.charAt(j)) {
                if(j==pattern.length()-1) {
                    count++;
                    list.add(i-pattern.length()+2);
//                    System.out.println(i-pattern.length()+2);
                    j=p[j];
                }else {
                    j++;
                }
            }
        }
        
        
        
    }
    
    static int[] find(String pattern) {
        int[] p =new int[pattern.length()];
        int j=0;
        
        for(int i=1;i<pattern.length();i++) {
            while(j>0 && pattern.charAt(i) != pattern.charAt(j)) {
                j=p[j-1];
            }
            if(pattern.charAt(i)==pattern.charAt(j)) {
                j++;
                p[i]=j;
            }
        }
        
        return p;
    }
    
}