[알고리즘] KMP 문자열 매칭 알고리즘

안수진·2024년 5월 17일

Algorithm

목록 보기

17/22

문자열 매칭 알고리즘

문자열(parent)이 있을 때 그 문자열 안에서 특정한 패턴(pattern)을 찾는 알고리즘

💬 단순 비교 문자열 매칭 알고리즘

문자열(parent) =ABCDEF, 찾을 문자열(pattern) = DEF 인 경우
다음과 같은 방식으로 찾을 수 있다.

긴 글	B	C	D	E	F
찾을 문자열	D	E

먼저 찾을 문자열인 DE를 가장 앞 부분에 위치시키고 확인한다.
매칭이 이루어지지 않았으므로 한 칸 이동시킨다. 이후에는 다음과 같이 비교를 할 수 있게 된다.

긴 글	B	C	D	E	F
찾을 문자열		D	E

마찬가지로 매칭이 이루어지지 않았으므로 한 칸 더 이동하여 다음과 같이 배치하여 확인한다.

긴 글	B	C	D	E	F
찾을 문자열			D	E

위와 같이 매칭한 경우 정확히 매칭이 이루어진 것을 알 수 있다.
이러한 방식을 사용하면 O(N*M)의 시간 복잡도를 가지게 된다.

위와 같이 단순하게 모든 경우를 다 비교하는 경우는 최악의 경우 엄청난 시간이 소요될 수 있다.

예를 들어 길이가 10,000,000인 글에서 길이가 1,000인 부분 문자열을 찾으려는 경우
연산 양이 10,000,000,000이기 때문이다.

따라서 모든 경우를 다 비교하지 않아도 부분 문자열을 찾을 수 있는 KMP 알고리즘을 사용해야 한다.

📌 KMP(Knuth-Morris-Pratt)

KMP 알고리즘은 접두사와 접미사의 개념을 활용하여
반복되는 연산을 얼마나 줄일 수 있는지 판별하여 매칭할 문자열을 빠르게 점프하는 기법이다.

최대 일치 길이 테이블

예를 들어 abacaaba가 있다고 하자.

길이	문자열	최대 일치 길이
1	a	0
2	ab	0
3	aba	1
4	abac	0
5	abaca	1
6	abacaa	1
7	abacaab	2
8	abacaaba	3

위와 같이 접두사와 접미사를 구하게 되면 접두사와 접미사가 일치하는 경우에 한해서는 점프(jump)를 수행할 수 있다는 점에서 몹시 효율적이다.

이 테이블은 KMP 알고리즘에서 탐색 문자열의 접두사와 접미사의 일치 부분을 계산하여 배열의 형태로 저장하는 역할을 한다.

실패 함수(failure function)이라 부르기도 한다.
비교된 탐색 문자열의 부분 중, 접두사이면서 접미사인 최대 문자열을 구하여 배열의 형태로 저장한다.

계산된 배열을 참고하여 탐색 문자열을 이동시킨다.
불일치가 발생한 인덱스가 j라면
다음 비교를 위해 탐색 문자열의 위치를 table[j-1] 인덱스에 위치한다.

👩🏻‍💻 최대 일치 길이 테이블 구현

private static int[] makeTable(String pattern) {
		int patternSize = pattern.length();
		int[] table = new int[patternSize];
		int j = 0;
		
		for(int i = 1; i < patternSize; i++) {
			
			// 일치하지 않으면 이전 접두사로 이동
			while(j > 0 && pattern.charAt(i) != pattern.charAt(j)) { 
				j = table[j - 1];
			}
			
			if(pattern.charAt(i) == pattern.charAt(j)) {
				table[i] = ++j;
			}
		}
		
		return table;
	}

위와 같이 하나씩 접두사와 접미사를 늘려가며 비교하다가 일치하지 않는 경우가 발생하면
일치했던 부분까지 되돌아가서 다시 검사를 하는 방식으로 빠르게 최대 일치 길이 테이블을 만들 수 있다.

이제 이렇게 테이블을 만든 뒤에는 다음과 같이 문자열 매칭을 수행할 수 있다.

긴 글	찾을 문자열
ababacabacaabacaaba	abacaaba

이렇게 긴 글과 찾을 문자열이 주어졌다고 하자.

서로 다른 문자가 발견되면 일치하는 접두사 크기에 한해서만 부분 문자열의 인덱스를 이동 시킨다.

👩🏻‍💻 KMP 알고리즘 구현

import java.io.IOException;

public class KMP {
	
	private static int[] makeTable(String pattern) {
		int patternSize = pattern.length();
		int[] table = new int[patternSize];
		int j = 0;
		
		for(int i = 1; i < patternSize; i++) {
			
			// 일치하지 않으면 이전 접두사로 이동
			while(j > 0 && pattern.charAt(i) != pattern.charAt(j)) { 
				j = table[j - 1];
			}
			
			if(pattern.charAt(i) == pattern.charAt(j)) {
				table[i] = ++j;
			}
		}
		
		return table;
	}
	
	private static void KMP(String parent, String pattern) {
		int[] table = makeTable(pattern);
		int parentSize = parent.length();
		int patternSize = pattern.length();
		int j = 0;
		
		for(int i = 0; i < parentSize; i++) {
			while(j > 0 && parent.charAt(i) != pattern.charAt(j)) {
				j = table[j - 1];
			}
			if(parent.charAt(i) == pattern.charAt(j)) {
				if(j == patternSize - 1) {
					System.out.println((i - patternSize + 2) + "번째에서 찾음.");
					j = table[j];
				}
				else {
					j++;
				}
			}
		}

	}
	
	public static void main(String[] args) throws IOException{
		String parent = "ababacabacaabacaaba";
		String pattern = "abacaaba";
		KMP(parent, pattern);
	}
}