[Java] 백준 1786번 찾기 문제 - KMP 알고리즘

[Java] 백준 1786번 찾기 문제 - KMP 알고리즘

www.acmicpc.net/problem/1786

1786번: 찾기

 

문제 설명

 

 

내 코드

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

class Main {
	public static void main(String[] args) throws Exception {
		Scanner scanner = new Scanner(System.in);
		String T = scanner.nextLine();
		String P = scanner.nextLine();
		
		
		int [] KMPtable = new int[P.length()];
		
		int j=0;
		for(int i=1; i<P.length(); i++){
			while(j>0 && P.charAt(i) != P.charAt(j)){
				j = KMPtable[j-1];
			}
			if(P.charAt(i) == P.charAt(j)){
				KMPtable[i] = ++j;
			}
		}
		//System.out.println(Arrays.toString(KMPtable));
		
		int count =0;
		String result="";
		j=0;
		
		for(int i=0; i<T.length();i++){
			while(j>0 && T.charAt(i)!= P.charAt(j)){
				j = KMPtable[j-1];
			}
			if(T.charAt(i)==P.charAt(j)){
				if(j == P.length()-1){
					count++;
					result+=(i-P.length()+2)+" ";
					j = KMPtable[j];
				}
				else{
					j++;
				}
			}
		}
		
		System.out.println(count);
		System.out.println(result);
		
	}
}

 

 

 

🎨 Key Point 

 

단어 안에 단어가 몇번 ? 어디에? 포함되어있는 가를 묻는 문제이다

예를들어 I have an apple. I have a pen. 이라는 문장안에 have가 몇번 어느 위치에 있는지 알아내는 문제이다.

시간복잡도의 효율성을 생각하지 않는다면 매우 쉽게 풀 수 있으나, 이 문제가 어려운 이유는 O(n)의 시간복잡도로 풀어야 하기 때문이다. 

 

이러한 문자열 안에 문자열을 찾는 알고리즘을 하기 위해선 KMP알고리즘 을 알아야 한다.

KMP 알고리즘은 접두사로 접미사에 얼마나 연속적으로 나오는지 O(n)에 가까운 성능 으로 int Table 배열을 만드는 것이다. 

찾을 문자열을 P , 찾아야하는 대상의 문자열을 T라고 하면 P<T 라는 전제하에 풀어도 된다. P>T라면 0개 발견될 것이기 때문이다. 

우선 찾을 문자열의 P에 얼마나 많은 반복 문자열이 나오는지 조사를 하기 위해 우선 KMP알고리즘을 이용하여 Table을 만들어 놓는다.  [코드 11-21번 줄]