BJ1786 찾기 (KMP 알고리즘)

https://www.acmicpc.net/problem/1786

KMP 알고리즘을 활용하는 문제다.

부분 일치 테이블과 두개의 포인터를 활용해 문자열 속에서 원하는 문자열을 찾는 효율적인 방법이다.

package day0224;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

// KMP 알고리즘(Knuth–Morris–Pratt Algorithm) 
// O(N+M)

public class String_KMPTest {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		char[] text = br.readLine().toCharArray();
		char[] pattern = br.readLine().toCharArray();

		int tLength = text.length, pLength = pattern.length;

		// 부분일치테이블 만들기 : KMP의 아이디어를 똑같이 적용, W에서 W를 찾는 듯한 행위를 해서...
		int[] pi = new int[pLength];
		for (int i = 1, j = 0; i < pLength; i++) {// i:접미사 포인터(i=1부터 시작: 우리는 부분일치테이블를 만드는게 목적이므로 첫글자 틀리면 0위치로 가야하므로.),
													// j:접두사 포인터
			while (j > 0 && pattern[i] != pattern[j])
				j = pi[j - 1];

			if (pattern[i] == pattern[j])
				pi[i] = ++j;
			else
				pi[i] = 0;
		}

		int cnt = 0;
		ArrayList<Integer> list = new ArrayList<Integer>();
		// i : 텍스트 포인터 , j: 패턴 포인터
		for (int i = 0, j = 0; i < tLength; ++i) {

			while (j > 0 && text[i] != pattern[j])
				j = pi[j - 1];

			if (text[i] == pattern[j]) { // 두 글자 일치
				if (j == pLength - 1) { // j가 패턴의 마지막 인덱스라면
					cnt++; // 카운트 증가
					list.add((i + 1) - pLength);
					j = pi[j];
				} else {
					j++;
				}
			}
		}

		bw.append(cnt + "\n");
		if (cnt > 0) {
			for (Integer i : list) {
				bw.append(Integer.toString(i + 1) + " ");
			}
		}
		bw.flush();
	}
}