[BOJ] 백준 16916번 부분 문자열 KMP (Java)

#16916 부분 문자열

난이도 : 골드 4

유형 : 문자열/ KMP

16916번: 부분 문자열

▸ 문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

▸ 입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

▸ 출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

 

문제 풀이 

두 문자열의 길이는 최대 100만이다. 이 두 문자열을 2중 for문을 써서 문자열 매칭을 하면 100만 * 100만으로 엄청난 시간이 걸릴 것이다. 두 문자열을 이러한 연산을 줄여주는 KMP 문자열 매칭 알고리즘을 사용하면 된다. KMP는 접두사와 접미사의 개념을 활용하여 모든 경우를 계산하지 않고 반복되는 연산을 줄여나가 매칭 문자열을 빠르게 점프하는 기법으로 효율적으로 문자열 매칭을 이루어나간다.

 

abacaaba가 있을 때 다음과 같다.

 

▸ 접두사 aba

▸ 접미사 aba

   

일치하는 접두사와 접미사의 최대길이는 aba로 3이다. 해당 탐색한 결과를 table[] 배열에 저장하면 다음과 같이 저장된다.    

   

‣ table[]   

a	b	a	c	a	a	b	a
0	0	1	0	1	1	2	3

 

이렇게 접두사와 접미사가 일치하는 최대길이를 찾았는데 이것으로 무엇을 해야할까? 

 

 

위와 같은 경우 접두사와 접미사가 일치하는 경우에 문자열 매칭을 탐색할 때 점프를 할 수 있어서 굉장히 효율적으로 작동하게 된다. 두 문자열을 비교하여 접두사와 접미사의 일치하는 최대의 길이를 찾는 예시를 풀어나가면서 이해해보자.

• 검색할 문자열(parent): ababacabacaaba
• 찾는 문자열(find): abacaaba

 

1. 찾는 문자열(find)의 접두사 접미사 최대길이를 저장하는 table[] 배열을 생성한다.

int[] table = makeTable(pattern);

 

2. 이제 table함수를 이용하여 parent 문자열과 find 문자열을 index 0부터 비교한다.

a) idx>0, parent의 i번째 문자 != find의 j(idx)번째 문자

• idx = table[idx-1];

☞  문자열 매칭이 시작된 후 연속적으로 매칭이 되지않을때 다시 매칭을 시작해야 하므로 idx값을 다시 돌려준다.

그런데 만약 문자열 매칭된 부분이 접두사와 접미사가 같은 구간이라면 idx는 0이아닌 그 일치하는 길이만큼의 값을 받게된다. 그러므로 앞에 접두사부분을 생략하고 다시 재빠르게 탐색이 가능해진다.

     

b) parent의 i번째 문자 == find의 j(idx)번째 문자

• if( idx == find문자열 길이-1) : 탐색 종료
• else  :  idx값 1증가

 

  ☞  idx값이 find문자열 길이-1까지 도달했다면 문자열 매칭을 성공한 것이므로 탐색을 종료한다. 아니면 일치할 때마다 idx값을 1증가하여 다음 문자를 매칭하도록 한다.

 

위와 같은 방식으로 코드를 풀어나가면 된다. 자세한 탐색과정을 보려면 여기로

 

 

KMP 문자열 매칭 알고리즘은 탐색시간을 위와 같은 방식으로 줄여준다. 그래서 시간복잡도도 기존 단순 문자열 매칭 알고리즘은 O(n*m)이지만 KMP는 table생성할 때 반복문 한번, kmp 매칭할 때 한번 해서 O(n+m)으로 굉장히 줄여준다.

 

풀이 코드 

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s1 = br.readLine();
		String s2 = br.readLine();
		
		System.out.println(KMP(s1, s2));
		
	}
	
	static int KMP(String parent, String pattern) {
		int[] table = makeTable(pattern);
		int n1 = parent.length();
		int n2 = pattern.length();
		
		int idx = 0;
		for(int i=0; i< n1; i++) {
			while(idx>0 && parent.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			
			if(parent.charAt(i) == pattern.charAt(idx)) {
				if(idx == n2-1) {
					idx =table[idx];
					return 1; // 매칭이 되었으면 1  
				}else {
					idx += 1;
				}
			}
		}
		 
		return 0; // 매칭이 안되었으면 0 
		
	}
	
	static int[] makeTable(String pattern) {
		int n = pattern.length();
		int[] table = new int[n];
		
		int idx=0;
		for(int i=1; i<n; i++) {
	        // 일치하는 문자가 발생했을 때(idx>0), 
			// 연속적으로 더 일치하지 않으면 idx = table[idx-1]로 돌려준다.
			while(idx>0 && pattern.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			
			if(pattern.charAt(i) == pattern.charAt(idx)) {
				idx += 1;
				table[i] = idx;  
			}
		}
		
		return table;
 	}
}