[KMP] 찾기(백준 1786번, 자바)

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

1786번: 찾기

 

KMP 알고리즘 

- 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행 

- 시간 복잡도: O(M+N)

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

public class Main {

	static String T;
	static String P;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T=br.readLine();
		P=br.readLine();
		
	
		int[] p=getP();
		
		int answer=0;
		StringBuilder sb=new StringBuilder("");	
		
		int j=0;
		int cnt=0;
		
		for(int i=0;i<T.length();i++) {
			if(T.charAt(i)!=P.charAt(j)) {
				if(j==0) continue; 
				else {
					j=p[j-1];
					i--;			
				}
			
			}
			else {
				if(j==P.length()-1) { //P길이의 문자를 찾으면 
					answer++;
					sb.append((i-j+1)+" ");
					cnt=0;
					j=p[j]; //j값은 p[j]로 저장 
				}
				else j++;
			}
		}
		
		System.out.println(answer);
		System.out.println(sb.toString());
	}
	 
    //pi배열 
	static int[] getP() {
		
		int[] pi=new int[P.length()];
		pi=new int[P.length()];
		int j=0;
		pi[0]=0;
		
		for(int i=1;i<P.length();i++) {
			if(P.charAt(i) != P.charAt(j)) { //다르면
				if(j==0) continue; //1. j가 0이면 i만 증가
				else {
					j=pi[j-1]; //2. j=p[i-1]로 변경
                    i--; //i는 한번 더 비교  
				}
			}
			else { //문자가 같다면
				pi[i]=j+1; // 연속하는 문자의 개수 저장   
				j++; //i와 j 모두 증가
			}
		}
		
		return pi;
		
	}
	
}