Kmp 문자열 탐색

문자열 탐색 비교

kmp(Knuth-Morris-Pratt) 알고리즘은 문자열 탐색시 불필요한 탐색과정을 없애주는 알고리즘이다. 문자열과 검색할 문자열의 겹치는 부분을 찾아 검사를 시작할 위치를 구한다. 예를 들어 아래와 같이 ZABCABCABD에서 ABCABD를 찾을 경우이다.

왼쪽의 단순 문자열 탐색은 하나씩 차례되로 비교한다. 반면에, kmp 알고리즘은 2번 과정에서 txt(text)의 ABCABC와 pat(patter의 pat)의 ABCABD에서 C와 D가 불일치 이후 3번 과정을 보자. 2번 과정에서 txt에서 이미 검색했던 AB부분으로 pat의 접두 부분(AB)으로 이동한다고 생각하면 된다. 이때, 검색은 AB부분 뒤인 C부터 다시 시작한다. 따라서 pat의 C부터 검색을 하여 4번 과정이 진행된다.

예를들어, txt의 문자열의 길이가 n이고 pat 단순 문자열의 길이가 m이라면 단순 문자열 탐색에서 최악의 경우 시간복잡도는 O(mn)이다. kmp을 사용하여 비교 횟수의 상당 부분을 줄일수 있다. kmp는 최악의 경우에도 txt 길이만큼 비교하여 시간복잡도는 O(n)이다.

kmp 구현

1. kmp을 구현하기 위해서는 문자열 txt에서 pat을 탐색하는 과정해서 불일치 하면, 다시 검색할 pat의 위치를 알아야한다. 허나 할때마다 위치를 구하는거는 비효율적이므로 미리 위차가 저장된 테이블을 만들어 주어야한다. 따라서 skip table을 만들어 준다.

2. 중복되는 문자의 나열을 구하여야한다. 그러기 위해서는 접두사와 접미사 개념을 이용하여야한다. 위의 그림을 보면 검색완료 후, 불일치시 txt의 AB(pat의 접미사)와 pat의 AB(접두사)가 겹치는 것을 볼수 있다. 그리고 나서 txt의 AB(pat의 접미사) 부분으로 pat AB(접두사)가 움직이며, 이미 AB는 같기 때문에 C부터 검색을 시작하면된다. 따라서 검색할 문자열 pat의 접두사와 접미사을 활용하여 구현 하여야한다.

접두사와 접미사를 구하기 위해, 검색할 문자열 pat 두 개를 한 칸 뒤로 겹쳐 검색을 한다. 간단히 말해서, 접두사와 접미사가 일치한 수만큼 skip table에 값을 저장한다. 1 ~ 2번 과정은 겹치는 문자가 없으므로 0을 저장한다. 3번 과정은 A가 겹치므로 1을 저장하고, 4번은 AB가 겹치므로 2를 저장한다. 4번은 불일치하므로 0을 저장한다. 이렇게 되면 txt에서 pat을 검색할때, pat이 불일치하는 문자의 위치(인덱스)로 skip table에 접근하여 다시 검색할 위치(인덱스)를 가져올수 있다.

kmp 알고리즘

#pragma warning (disable:4996)
#include <stdio.h>

/*--- txt 문자열 내에서 pat 문자열 검사 ---*/
int kmp_match(const char txt[], const char pat[]) 
{
	int pt = 1; // txt 커서
	int pp = 0; // pat 커서
	int skip[1024]; // txt와 pat이 겹치는 부분 찾아 검사를 시작할 위치 저장

	/* pat내의 중복된 문자열(접두사, 접미사) 검색 및 테이블 Set */
	while (pat[pt] != '\0') {
		if (pat[pt] == pat[pp]) // 문자 일치시
			skip[pt++] = ++pp; // 검사 시작할 문자 저장
		else if (pp == 0) // 처음부터 봐야할 경우
			skip[pt++] = pp; // 다음 문자 이동 및 0 저장
		else // 문자 불일치시
			pp = skip[pp - 1]; // 검사 시작할 위치로
	}


	/* txt내에서 pat 검색 */
	pt = pp = 0; // txt 커서, pat 커서 초기화
	while (txt[pt] != '\0' && pat[pp] != '\0') {
		if (txt[pt] == pat[pp]) { // 문자 일치시
			pt++;  pp++; // 다음 문자로(두 커서 1씩 뒤로 이동)
		}
		else if (pp == 0) // pat 첫 문자부터 검색
			pt++; // txt 다음 문자로
		else
			pp = skip[pp - 1]; // 검사 시작할 위치로
	}

	if (pat[pp] == '\0') // pat 검색 확인시
		return pt - pp; // 어느 인덱스부터 일치하는지 반환
	return -1; // 실패할 경우 -1 반환
}

int main(void)
{
	int idx;
	char s1[256];		/* 텍스트 */
	char s2[256];		/* 패턴 */

	puts("kmp법");
	printf("텍스트 : ");
	scanf("%s", s1);
	printf("패턴 : ");
	scanf("%s", s2);

	idx = kmp_match(s1, s2);	
	if (idx == -1)
		puts("텍스트에 패턴이 없습니다.");
	else
		printf("%d번째 문자부터 match합니다.\n", idx + 1);

	return 0;
}