[KMP알고리즘]b1786_찾기

1786번: 찾기

그냥 수업시간에 한 코드를 바꾸니까 맞았지만 KMP의 알고리즘 이해는 안됐다,, 다시 봐야함ㄹ

package w0923;

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		char[] text = in.readLine().toCharArray();
		char[] pattern = in.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:접두사 포인터
			// 자신의 패턴안에서 찾는다.. 일치하지 않을때는 j포인터가 앞으로 가면서 맞춘다
			while (j > 0 && pattern[i] != pattern[j])
				j = pi[j - 1];

			if (pattern[i] == pattern[j])
				pi[i] = ++j; // 일치하면 증가, 일치하지 않을 땐 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가 패턴의 마지막 인덱스라면
					list.add((i + 2) - pLength);
					sb.append(list.get(cnt)+" ");
					cnt++; // 카운트 증가
					j = pi[j];
				} else {
					j++; // j를 처음부터 다시 비교하지 않고 증가시키는 이유는 이전에 일치했던 패턴을 다시확인하기때문
				}
			}
		}

		bw.append(cnt+"\n"+sb);
		bw.flush();
		bw.close();
		in.close();

	}
}