문자열 찾기(매칭)_KMP알고리즘 [1/2]

[ KMP 알고리즘이란? ]

• 문자열의 가장 앞부분과 동일한 문자열 정보를 배열로 만들어 효율성을 검색의 높이는 방법
• 모두 다른 문자로 이루어진 문자라 하더라도 검색 효율성이 더 높음​

개념 이해가 잘 안돼서 한참 고민했습니다. 사전에 유의해야 할 사항은 만약 "ababab"라는 문자열에서 "abab"를 찾는다고 했을 때, 2개가 검색이 돼야 한다는 점입니다. 하나만 검색되면 틀린 로직입니다.

 

---

 

[ 일반 로직 ]

일반적인 로직 입니다. 먼저 첫 글자가 같으면 비교를 시작합니다.

 

 

끝까지 같지 않고 다른 글자가 나오면 다시 앞으로 이동해서 반복합니다. 만약 여기서 i가 그 자리에서 계속 전진만 하면 아까 "ababab"에서 "abab"를 찾을 경우 처음 네 글자 하나밖에 찾을 수가 없게 됩니다. 따라서 i의 위치도 계속 앞으로 옮겨줘야 합니다.

 

 

 

헷갈리지 않게 "ababab" 문자열을 예로 든다면 아래와 같습니다. 이렇게 i 위치를 다시 앞으로 이동시켜주고 계속 반복수행해야 "abab"를 두 개 찾을 수 있습니다.

 

 

 

 

---

위 로직의 코드입니다. 반복 수행횟수가 24번 정도 나오네요.

 

#include <stdio.h>
#include <string.h>

int main()
{
	int count = 0;
	char str[] = "abcabdabcabca";
	char find[] = "abca";

	unsigned i = 0, i2 = 0, f = 0;

	printf("\n  일치점 : ");
	while (i < strlen(str) - strlen(find) + 1)
	{
		count++;
		while (str[i2] == find[f] && f < strlen(find))
		{
			i2++;
			f++;
			count++;
		}

		if (f > strlen(find) - 1)
			printf("%d ", i);

		f = 0;
		i2 = ++i;
	}
	printf("\n  count : %d\n", count);
}

 

---

 

[ KMP 알고리즘 ]

KMP 알고리즘에서는 접두사와 접미사라는 개념을 이용해여 일반 로직처럼 i가 전진하다가 다시 앞으로 돌아오는 일이 없도록 해 검색 효율성을 높여줍니다.

 

※ 접두사와 접미사
해당 문자를 기준으로 가장 앞 문자열과 같은 문자가 몇개인가 하는 의미라고 보면 됩니다. 앞에 있는 문자열을 접두사, 뒤의 문자열을 접미사라고 합니다.

a : 0
ab : 0 0
aba : 0 0 1
abab : 0 0 1 2

위와 같이, 뒤의 a 입장에서는 가장 앞과 똑같은 글자가 1개인 것이고, b입장에서는 앞의 a를 포함해 ab 두 글자가 같으니 똑같은 글자가 2개라는 뜻입니다. A[0~1] == A[2~3]이라는 뜻으로 보면 됩니다.

 

접두사/접미사 개념이 도입된 이유는 일반 로직처럼 앞으로 다시 돌아가지 않도록 하기 위함입니다. 아래 예시를 보면 "abab"를 한번 찾고 다시 앞으로 돌아가서 확인하지 않아도 되는 이유를 알 수 있습니다. 접두사/접미사 정보를 이용해 앞을 이미 확인한 셈이 되는 거죠.

​

직관적으로 이해가 좀 어렵지만 생각해보면 간단한 삼단논법의 원리입니다. 현재 str[3]에서 멈췄을 때 기준으로 보면 str[0~3] == A[0~3]입니다. 그리고 A[3]의 접두사/접미사 정보가 '2'이라는 말은 결국 str[2~3] == A[2~3] == A[0~1] 이라는 뜻으로, str[4]는 A[2]부터 비교를 시작하면 되는 것이죠. 즉, str[3] → str[4]로 계속 전진하면서 확인할 수 있게 됩니다. 앞으로 돌아가서 다시 확인할 필요가 없어지는거죠.

 

 

 

 

---

 

 

KMP 알고리즘 코드입니다. 반복 횟수가 16정도로 일반 로직 대비 더 줄어든 것을 알 수 있습니다. 물론 하나의 반복문 안에서 처리하는 연산 수가 다른 경우 반복 횟수 자체만으로는 성능 비교가 어렵긴 합니다만, 이미 검증된 알고리즘이니 모든 연산에 count를 걸어보진 않겠습니다. 다들 C++로 작성해서 C로는 모범답안이 없지만 아마 비슷하지 않을까 싶습니다. 

 

#include <stdio.h>
#include <string.h>

int main()
{
	int count = 0; // 반복문 카운트
	char str[] = "abcabdabcabca";
	char find[] = "abca";
		
	/* 접두사/접미사 배열 생성 */
	int W[4] = { 0 };
	for (int i = 0, j = 1, status = 0; find[j] != '\0'; ++j)
	{
		if (find[i] == find[j])  // 첫 글자와 같은 글자가 나오면 
		{
			i++;  // 둘 다 한칸씩 이동하고 (for문에서 j++)
			W[j] = ++status;  // status 증가시켜서 배열값에 넣어줌
		}
		else if (i > 0)  // 같지 않은 경우
		{
			i = 0;  // 첫글자로 다시 돌아오고
			W[j] = status = 0;  // status 0으로 초기화해서 배열값에 넣어줌
		}
	}
	
	/* KMP 알고리즘 수행 */	
	printf("\n  %s\n  %s  \n  일치점 : ", str, find);
	for (unsigned s = 0, f = 0; s < strlen(str);)
	{
		count++;
		while (str[s] == find[f] && f < strlen(find))
		{
			count++;
			s++;
			f++;
		}

		if (f > strlen(find) - 1)  // 완전한 문자열 찾았을 경우
		{
			printf("%d ", s - f);  // 시작점 출력
			f = W[f - 1];  // 배열값이 find의 인덱스가 됨
		}
		else  // 찾기 전에 다른 문자가 나올 경우
		{
			if (W[f] == 0)
				f = 0;  // W값이 0이면 0으로 이동
			else if (W[f] > 0)  // W값이 0보다 크면
				f = W[f] - 1;  // 해당 W값보다 한 칸 앞으로 이동
			s++;  // 뒷글자로 이동
		}
	}
	printf("\n  count : %d\n", count);
}