[알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘)

밑에 보이는 예시는 KMP 알고리즘 사용 전인데 효율이 떨어져 보입니다.

텍스트와 패턴이 일치하는지 차례대로 순회하면서 비교해보기 때문에 시간복잡도는 O(문자열 길이 * 패턴 길이) = O(N)으로, 시간이 오래 걸립니다.

 

KMP 알고리즘 사용 X

 

KMP 알고리즘 사용 O

KMP 알고리즘이란?

 

패턴과 텍스트의 불일치를 감지할 때마다 그 전에 검사해왔던 텍스트의 문자들이 무엇인지 알고 있습니다(처음 검사할 때 A B A B 로 B에서 불일치가 발생했을 때, 불일치 발생 전 문자들이 A, B, A).

KMP 알고리즘은 이를 이용해 불필요한 검사는 스킵합니다. 

시간 복잡도는 최악의 경우, O(문자열 길이 * 패턴 길이) 이므로 위와 같이 O(N)입니다. 

 

알고리즘 구성

 

lps[ ] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대 길이를 저장하는 배열 (밑에서 설명 예정)

pat[ ] : 패턴 문자열

txt[ ] : 주어진 텍스트

 

- 함수

1) KMP 알고리즘 수행 함수

2) lps 배열 구성 함수

 

 

다음은 ABAABAB라는 문자열을 가지고 lps[ ]를 구성하는 예입니다.

 

i	문자열	lps[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

 

이와 같이 접두사와 접미사가 같을 때, 그 최대 길이를 가지고 있는 배열이 바로 lps[ ]입니다. 

(만약에 ABABABAB 라는 문자열이면 4가 lps에 들어갈 것입니다.)

---

 

lps 배열 구성 함수

i 는 접미사 가리키는 인덱스, len은 접두사 가리키는 인덱스입니다.

 

- 1번째

len = 0 일때

len과 i의 글자 불일치

-> i만 증가, lps[i] = 0

- 2번째

글자 일치

-> len과 i 둘 다 증가

lps[i] = len

- 3번째

불일치

-> len = lps[len-1]

- 4번째

일치

 

 

- 5번째

일치

- 6번째

일치

- 7번째

불일치

-> len = lps[len-1]

- 8번째

일치

 

 

 

 

※ 7번째 붙임설명

6번째에 len = 2, i = 5일 때, A가 이미 일치했던 사실을 알기 때문에 이를 이용하기 위해

len은 lps[len - 1]로 이동하는 것입니다. 이는 KMP 알고리즘 원리와 같습니다.

 

---

kMP 알고리즘 실행 함수

설명에 앞서 위 함수를 실행한 과정을 보여드리겠습니다.

 

 

 

노란색일 때, 일치했을 때입니다.

KMP 알고리즘에서는 일치했을 때에도,

불일치했을 때와 마찬가지로 그 전까지는 일치했다는 것을 이용해 몇 글자 건너서 검사를 다시 시작합니다.

 

만약 패턴이 BABA 이었을 때 일치를 했다면 아마 이런 식이었겠죠?

 

 

 

다른 패턴과 텍스트로 실행한 과정입니다.

 

 

 

전체 코드와 실행과정입니다.

 

 

#include <string>
#include <iostream>

void computeLPSArray(char* pat, int M, int* lps);

void KMPSearch(char* pat, char* txt)
{
	const int M = strlen(pat);
	int N = strlen(txt);
	int* lps = new int[M] {0};
	computeLPSArray(pat, M, lps);
	
	int i = 0;
	int j = 0;
	while (i < N) {
		if (pat[j] == txt[i]) {
			j++;
			i++;
		}
		if (j == M) {
			printf("Found pattern at index %d", i - j);
			j = lps[j - 1];

		}

		else if (i < N && pat[j] != txt[i]) {
			if (j != 0)
				j = lps[j - 1];
			else
				i = i + 1;
		}
	}
	delete[] lps;
}

void computeLPSArray(char* pat, int M, int* lps)
{
	int len = 0;
	lps[0] = 0;

	int i = 1;
	while (i < M) {
		if (pat[i] == pat[len]) {
			len++;
			lps[i] = len;
			i++;
		}
		else
		{
			if (len != 0) {
				len = lps[len - 1];
			}
			else {
				lps[i] = 0;
				i++;
			}
		}
	}
}

int main()
{
	char txt[] = "ABABDABACDABABCABAB";
	char pat[] = "ABABCABAB";
	KMPSearch(pat, txt);
	return 0;
}

 

Found pattern at index 10

 

 

오류 또는 오타가 있다면 알려주시면 감사하겠습니다. :)