아이디어

• KMP 알고리즘의 튜토리얼 격 문제
  • 패턴 매칭 중 불일치가 발견되면 다음 탐색은 처음부터가 아닌 해당 불일치가 발견되기 전까지의 서브패턴 중 반복되는 패턴 부분으로 돌아가는 방법
  • 이를 위해 pi[]라는 배열을 만든다.
    * pi[i]: P[0..i] 서브패턴의 앞의 k글자와 뒤의 k글자가 일치하는 k의 최댓값
  • 뒤의 반복부분을 앞의 반복 부분으로 당겨 그 부분부터 새로 탐색을 이어감

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	
	static char[] T, P;
	static int n, m, ans;
	static int[] pi;

	public static void main(String[] args) throws Exception {
		T = rd.readLine().toCharArray();
		P = rd.readLine().toCharArray();
		n = T.length;
		m = P.length;
		
		if (n < m) {
			System.out.println(0);
			return;
		}
		
		// pi[] 만들기
		pi = new int[m];
		int j = 0;
		for (int i=1; i<m; i++) {
			while (j > 0 && P[i] != P[j]) j = pi[j-1];
			if (P[i] == P[j]) pi[i] = ++j;
		}
		
		// T와 P 비교
		j = 0;
		for (int i=0; i<n; i++) {
			while (j > 0 && T[i] != P[j]) j = pi[j-1];
			if (T[i] == P[j]) {
				j++;
				if (j == m) {
					ans++;
					sb.append(i-m+1 + 1).append(' ');
					j = pi[j-1];
				}
			}
		}
		
		System.out.println(ans);
		System.out.println(sb);
	}
}

메모리 및 시간

• 메모리: 39604 KB
• 시간: 512 ms

리뷰

• 지문이 너무 친절해서 당황했다.
• 하지만 KMP는 아직 설명하라 하면 완벽히 못 하겠다...