[BOJ] 1786 찾기 (Java)

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

알고리즘

KMP

풀이

KMP 알고리즘을 그대로 적용시켜 풀면 된다

코드

import java.io.*;
import java.util.*;

public class Main {
	static char[] text, pattern;
	static int tLen, pLen;
	static ArrayList<Integer> list;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		text = br.readLine().toCharArray();
		pattern = br.readLine().toCharArray();
		
		tLen = text.length;		// 입력받은 텍스트의 길이 
		pLen = pattern.length;		// 비교할 패턴의 길이 
		
		int[] pi = new int[pLen];	// 실패함수를 만들기 위함
		
	    for(int i=1, j=0; i<pLen; ++i){
	    	// i:접미사 포인터
	    	// j:접두사 포인터
	        while(j > 0 && pattern[i] != pattern[j]) j = pi[j-1];  
	        if(pattern[i] == pattern[j]) pi[i] = ++j;
	    }
		
		int cnt = 0;
		list = new ArrayList<Integer>();
		// i : 텍스트 포인터
        	// j: 패턴 포인터 
		for(int i=0, j=0; i<tLen; ++i) { 
			
			while(j>0 && text[i] != pattern[j]) j = pi[j-1]; 
			
			if(text[i] == pattern[j]) { 		// 두 글자 일치할 경우
				if(j == pLen-1) { 		// j가 패턴의 마지막 인덱스라면 
					cnt++; 			// 카운트 증가
					list.add((i+1)-pLen); 	// 리스트에 시작 인덱스 정보 추가 
					j=pi[j]; 
				} else j++;
			}
		}
		
		System.out.println(cnt);
		for(int i=0; i<cnt; i++) System.out.println(list.get(i)+1);
		br.close();
	}
}