#10 KMP 문자열 매칭

단순 비교 문자열 매칭

1.단순 비교 문자열 매칭 알고리즘은 두 문자열을 처음부터 끝까지 계속 비교하는 알고리즘입니다.

2.단순 비교 문자열 매칭 알고리즘은 O(NM)의 시간 복잡도를 가집니다.

 

ex) ABCDEFG 에서 EF를 찾는 경우

AB랑 EF를 비교,  BC랑 EF를 비교 ... 이런식으로 하나하나 찾아 나간다.

 

코드예시

#include <stdio.h>
#include <string.h>
char* parent = "ABCDEFG";
char* pattern = "EF";
int main(void) {
	int parentSize = strlen(parent);
	int patternSize = strlen(pattern);
	for (int i = 0; i <= parentSize - patternSize; i++) {
		int found = 1;
		for (int j = 0; j < patternSize; j++) {
			if (parent[i + j] != pattern[j]) { found = 0; break; }
		}
		if (found) {
			printf("%d번째에서 찾았습니다.\n", i + 1);
		}
	}
	system("pause");
}

결과 값

---

KMP 문자열 매칭

 

1.단순 비교 문자열 매칭 알고리즘은 O(NM)의 시간 복잡도로 상당히 비효율적이다.

2.KMP 문자열 매칭 알고리즘은 O(N+M)의 시간 복잡도로 문제를 해결 할 수 있다.

 

 

KMP 알고리즘은 접두사와 접미사가 일치하는지를 활용해 빠르게 문자열 매칭을 수행하는 알고리즘이다.

 

접두사와 접미사
특정한 부모 문자열에서 찾고자 하는 패턴(Pattern) 문자열이 “abacdab”라고 가정해봅자.

이 때 각 길이에 따른 접두사와 접미사가 일치하는 최대 길이를 구한다.

 

 

테이블 만들기

j=0, i=1로 설정하고 테이블 만들기를 진행한다.

 

pattern[j]와 pattern[i]가 일치하는지 반복적으로 확인한다.

일치하는 경우 j에 1을 더한 뒤에 j의 인덱스를 table[i]에 삽입한다.

 

실제로 문자열 매칭을 진행할 때에도 불일치하는 경우 j를 ‘마지막으로 일치했던 순간’까지의 인덱스로 이동해
다시 검사한다.

‘마지막으로 일치했던 순간’은 table[j – 1]이다.

 

코드예시

//문자열 정의
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* parent = "acabacdabac";
char* pattern = "abacdab";

//테이블 생성함수 구현
int* makeTable(char* pattern) {
	int patternSize = strlen(pattern);
	int* table = (int*)malloc(sizeof(int) * patternSize);
	for (int i = 0; i < patternSize; i++) {
		table[i] = 0;
	}
	int j = 0;
	for (int i = 1; i < patternSize; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j]) {
			table[i] = ++j;
		}
	}
	return table;
}

//KMP함수 구현
void KMP(char* parent, char* pattern) {
	int* table = makeTable(pattern);
	int parentSize = strlen(parent);
	int patternSize = strlen(pattern);
	int j = 0;
	for (int i = 0; i < parentSize; i++) {
		while (j > 0 && parent[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (parent[i] == pattern[j]) {
			if (j == patternSize - 1) {
				printf("[인덱스 %d]에서 매칭 성공\n", i - patternSize + 2);
				j = table[j];
			}
			else {
				j++;
			}
		}
	}
}

//사용
int main(void) {
	KMP(parent, pattern);
	system("pause");
}

 

결과 값