[JAVA] 백준 1786 찾기

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

1786번: 찾기

 

풀이

 

코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		char[] text = in.readLine().toCharArray();
		char[] pattern = in.readLine().toCharArray();
		
		int tLength = text.length, pLength = pattern.length;
		
		int[] pi = new int[pLength]; //패턴 포인터를 어디로 옮겨야하는지 인덱스 저장
	    for(int i=1, j=0; i<pLength; i++){// i:접미사 포인터, j:접두사 포인터
	        while(j>0 && pattern[i] != pattern[j]) {
	        	j = pi[j-1]; //j에서 문자가 다르다! -> j-1까지는 동일하다, pi[j-1]로 j 포인터를 이동
	        }
	        if(pattern[i]==pattern[j]) pi[i] = ++j; //j와 i는 일치하면 j 증가, 길이는 j+1
	        else pi[i] = 0; //일치하지 않는다면 j 그자리에
	    }
		
		int cnt = 0;
		// 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++; // 카운트 증가
					sb.append((i+1)-pLength+1).append('\n'); 
					j=pi[j]; 
				}else { // 패턴 앞쪽 일치하며 진행중인 상황
					j++;
				}
			}
		}
		
		System.out.println(cnt);
		System.out.println(sb);
	}

}