[알고리즘 정리] KMP, 문자열 패턴 매칭 알고리즘

 

다룰 내용

• Brute-Force로 패턴 매칭
• KMP 알고리즘이란 무엇인가?
• KMP 알고리즘 구현

 

---

 

Brute-Force로 패턴 매칭

기존에 있는 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴과 일치하는지 일일이 확인하는 방식으로 동작하게 됩니다. 기존 문자열을 패턴 길이만큼 비교해보기 때문에 시간 복잡도는 O(문자열 길이 * 패턴 길이)가 됩니다. 

 

위의 그림처럼 하나 하나 일치하는지 비교를 하기 때문에 문자열의 길이가 길어진다면 비효율적인 탐색이 됩니다.

 

 

---

 

KMP 알고리즘이란 무엇인가?

불일치가 발생한 텍스트 문자열의 앞부분에 어떤 문자가 있는지 미리 알고 있기 때문에 불일치가 발생한 앞부분에 대해서 다시 비교하지 않으면서 매칭이 일어나는지 판단할 수 있는 알고리즘입니다.

 

시간 복잡도는 O(문자열 길이 + 패턴 길이) 즉, 선형 시간에 수행을 마칠 수 있습니다.

 

 

그렇다면 왜 KMP 사용하는가?

만약 문자열의 길이가 100,000이고 패턴의 길이가 1,000일 때 

brute-force의 경우, 100,000 * 1,000이기 때문에 1억번 검사를 수행해야합니다. 반면 KMP의 경우 100,000 + 1,000이기 때문에 101,000번만에 검사가 가능합니다. 

 

문자열의 길이와 패턴의 길이가 길수록 두 방법의 시간 복잡도 차이는 확연히 드러나게 됩니다.

따라서 문제를 풀 때 주어진 입력 값의 최악의 경우를 보고 Brute-Force로 해결하기 어려운 문제라면 KMP를 사용할 수 있습니다.

 

KMP 알고리즘 동작

1. 먼저 패턴 문자열의 pi 배열을 만들어야 합니다. 
   1. 여기서 pi 배열이란 0 ~ i까지의 부분 문자열에서 접두사와 접미사가 얼마나 일치하는지 저장해놓은 배열입니다.
2. pi배열과 본문 문자열 길이를 매칭합니다.

 

1단계. Pi 배열을 생성해야 합니다.

 

Pi 배열 생성 과정

 

j는 접두사의 위치, i는 접미사의 위치를 의미합니다. 

기본적인 동작을 설명하면, j와 i가 일치했을 경우와 일치하지 않았을 때의 경우를 나눠서 생각해봐야 합니다.

• j 위치의 문자열과 i 위치의 문자열이 일치했을 경우: 그 위치에서 접두사와 접미사가 일치했다는 것이므로 다음 위치의 j와 i의 문자열도 일치하는지 검사해야 합니다. 따라서 j와 i의 위치를 한 칸씩 오른쪽으로 이동해줍니다.
• j 위치의 문자열과 i 위치의 문자열이 일치하지 않을 경우: 접두사와 접미사가 일치하지 않는다는 것이므로 다시 검사를 해야하는데 이때 아예 처음으로 돌아갈 수도 있으나 비효율적입니다. 그래서 여태까지 일치했던 곳에서부터 다시 검사를 하는 것이 유리합니다. 따라서 pi배열을 참고하여 j의 위치를 pi[j - 1]에서 가리키는 위치로 이동시켜봅니다. j - 1인 이유는 최소 j - 1 위치까지는 접두사와 접미사가 일치했다는 것이므로 이동을 최소화할 수 있기 때문입니다. 이동을 시킨 후 다시 일치하는지 검사를 합니다.

pi 배열을 만드는 과정은 아래와 같습니다.

 

 

 

 

 

 

---

문자열 매칭 동작 과정

 

2단계. 본문 문자열과 패턴을 비교합니다.

 

 

 

 

 

 

 

 

 

KMP 알고리즘 구현

 

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

public class KMP {

	public static int result, pi[];
	public static String origin, pattern;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		origin = br.readLine();
		pattern = br.readLine();
		
		pi = new int[pattern.length()];
		getPi();
		KMP();
	}
	
	private static void getPi() {
		int j = 0;
		for (int i = 1; i < pattern.length(); i++) {
			// 맞는 위치가 나올 때까지 j - 1칸의 공통 부분 위치로 이동
			while(j > 0 && pattern.charAt(i) != pattern.charAt(j)){
				j = pi[j - 1];
			}
			// 맞는 경우
			if(pattern.charAt(i) == pattern.charAt(j)) {
				//i길이 문자열의 공통 길이는 j의 위치 + 1
				pi[i] = ++j;
			}
		}
	}
	
	private static void KMP() {
		int j = 0;
		for (int i = 0; i < origin.length(); i++) {
			// 맞는 위치가 나올 때까지 j - 1칸의 공통 부분 위치로 이동
			while(j > 0 && origin.charAt(i) != pattern.charAt(j)) {
				j = pi[j - 1];
			}
			// 맞는 경우
			if(origin.charAt(i) == pattern.charAt(j)) {
				if(j == pattern.length() - 1) {
					result = 1;
					break;
				}
				//맞았지만 패턴이 끝나지 않았다면 j를 하나 증가
				else
					++j;
			}
		}
		System.out.println(result);
	}
}

 

 

---

Rabin-Karp 알고리즘이란 무엇인가?

문자열 검색을 위해 해시 값 함수를 이용하고, 패턴 내의 문자들을 다 비교하는 대신에 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시 값만을 비교하는 알고리즘입니다. 비교에 대한 부담을 brute-force보다는 줄이지만 최악의 시간 복잡도는 brute-force 와 같은 O(M * N)입니다. 그러나 평균적으로는 선형에 가까운 시간 복잡도를 보이는 알고리즘입니다.

 

 

Boyer-Moore 알고리즘이란 무엇인가?

뒤에서부터 탐색을 하는 알고리즘으로 오른쪽 끝에 있는 문자가 불일치이고 문자가 패턴 내에 존재하지 않는 경우 패턴의 길이 만큼 이동할 수 있습니다. 빠를 것 같지만 시간 복잡도는 O(M * N)입니다.