백준 1786번 (JAVA) 찾기

KMP 알고리즘을 사용하여 같은 문자열이 어느 위치(인덱스)에 몇번 나오는지 확인하는 문제이다.

 

KMP 알고리즘은 워낙 이해가 까다로운 알고리즘이므로, 관련 설명을 충분히 읽어보고 풀어보는 것을 추천한다.

 

bowbowbow.tistory.com/6#comment5168448

KMP : 문자열 검색 알고리즘

나에게는 이 곳의 설명이 굉장히 도움이 많이 되었다. 

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

public class BOJ_1786_찾기 {
	static String str;
	static String pattern;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		str = br.readLine();
		pattern = br.readLine();
		ArrayList<Integer> res = KMP();
		System.out.println(res.size());
		for (int i : res) {
			System.out.print(i + 1 + " ");
		}
	}

	private static ArrayList<Integer> KMP() {
		int[] pi = getPi();
		ArrayList<Integer> res = new ArrayList<Integer>();
		int j = 0;
		for (int i = 0; i < str.length(); i++) {
			while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
				j = pi[j - 1];
			}

			if (str.charAt(i) == pattern.charAt(j)) {
				if (j == pattern.length() - 1) {
					res.add(i - (pattern.length() - 1));
					j = pi[j];
				} else {
					j++;
				}
			}
		}

		return res;
	}

	private static int[] getPi() {
		int[] pi = 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 = pi[j - 1];
			}
			if (pattern.charAt(i) == pattern.charAt(j)) {
				pi[i] = ++j;
			}
		}
		return pi;
	}

}