[백준 1786] 찾기 (JAVA)

문제 링크: https://www.acmicpc.net/problem/1786

1786번: 찾기

1. 주의할 점

- KMP 알고리즘에 대하여 알고 있어야 한다

- 공백 문자도 받을 수 있어야 한다

- 애매하게 알고 있다면 이전 게시글을 참고한다 https://imnotabear.tistory.com/117

[백준 16916] 부분 문자열 (JAVA)

- 아예 모르면 위키피디아를 통해 KMP 알고리즘에 대해 공부하고 다시 문제를 풀도록 한다

 

2. 구현

- KMP 알고리즘을 통하여 구현한다

- 일치하는 문자열이 있는 경우, Cnt++를 시키고, 해당 Index를 Li 리스트에 담는다

- 모두 검사한 후, Cnt와 Li에 있는 원소를 전부 출력한다 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main_bj_1786_찾기 {
	static int cnt=0;
	static List<Integer> li;
	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;
	}
	
	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) {
					++cnt;
					li.add(i-j+1);
					j=pi[j];
				}
				else
					j++;
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String origin = br.readLine();
		String pattern = br.readLine();
		li = new ArrayList<>();
		KMP(origin,pattern);
		System.out.println(cnt);
		for(int i=0;i<cnt;i++)
			System.out.println(li.get(i));
	}
}