백준 1786 - 찾기

Java

1786 번 - 찾기

문제

문장 T와 패턴 P를 비교하여, T 중간에 P가 몇 번 나타나는지 횟수를 센다.
또한 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다.

접근 방법

KPM 알고리즘을 통하여 해결하였다.

코드

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String T = br.readLine();
    	String P = br.readLine();
    	
    	int tl = T.length();
    	int pl = P.length();
    	
    	int[] fail = new int[pl];
    	
    	// 실패 함수
    	int j = 0;
    	for(int i = 1; i < pl; i++) {
    		while(j > 0 && P.charAt(i) != P.charAt(j)) {
    			j = fail[j-1];
    		}
    		if(P.charAt(i) == P.charAt(j)) {
    			fail[i] = ++j;
    		}
    	}
    	int cnt = 0;
    	ArrayList<Integer> result = new ArrayList<>();
    	// 패턴
		// i : 텍스트 포인터 , j: 패턴 포인터 
    	j = 0;
    	for(int i = 0; i < tl; i++) {
    		while(j > 0 && T.charAt(i) != P.charAt(j)) {
    			j = fail[j-1];
    		}
    		if(T.charAt(i) == P.charAt(j)) {
    			if(j == pl - 1) {	// j가 패턴의 마지막 인덱스라면 
    				cnt++;
    				result.add(i - j + 1);
    				j = fail[j];
    			}
    			else {
    				j++;
    			}
    		}
    	}
    	System.out.println(cnt);
    	if(cnt > 0) {
    		for(int i = 0; i < result.size(); i++) {
    			System.out.print(result.get(i) + " ");
    		}
    	}
    	
    	br.close();
	}

	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

KPM KPM KPM

개선할 점