알고리즘 : 스트링 탐색 #1 (Naive, 직선적 알고리즘)

이 페이지에서 "KMP" 라는 글자를 찾고 싶다면 어떻게 해야할까요?

Ctrl + F 를 눌러서 "KMP"를 검색하면 됩니다.

이렇게 글에서 특정 단어를 탐색하는 과정을 지금부터 소개할 텐데요, 바로 스트링 탐색 알고리즘입니다.

---

직선적 알고리즘

---

Choi Yena is cute. ㄹㅇ

"Choi Yena is cute." 라는 문장에서 cute를 찾으려고 할 때, 어떻게 해야 할까요?

우선 여기서 "Choi Yena is cute."는 Text, "cute"는 Pattern이

라고 부릅니다.

각 스트링의 글자 갯수를 N, M이라 할 때, t[N] 배열과 p[M] 배열을 대조하면서 텍스트 내의 패턴을 찾는 것이 스트링 탐색 알고리즘이죠. 여기에는 대표적으로 네 가지 알고리즘이 있습니다.

1. 직선적 알고리즘 (Naive Search)
2. KMP 알고리즘
3. 보이어-무어 알고리즘 (BM)
4. 라빈-카프 알고리즘

우선 직선적 알고리즘은 영어 명칭에서 알 수 있듯 말그대로 나이브한 알고리즘 입니다.

t[0]과 p[0]을 비교하고, 틀리면 t[1]과 p[0]을 비교하고.... 이렇게 단순무식하게 한 글자씩 비교하며 진행합니다.

알고리즘을 확인하겠습니다.

BruteForce(p[], t[])
	M ← 패턴의 길이; N ← 텍스트의 길이;
	for(i ← 0, j ← 0; j < M and i < N; i ← i+1, j ← j+1) do // for((1); (2); (4))
		if(t[i] ≠ p[j]) then { // (3)
			i ← i-j;
			j ← -1;
		}
	if(j = M) then return i-M; // (5)
	else return i; // (6)
end BruteForce()

우선 M과 N을 구하는데, 스트링의 길이는 strlen으로 구할 수 있습니다.

다음으로 for문을 살펴보겠습니다. 주석처리 한 숫자를 확인하면서 따라오시면 됩니다.

① i, j = 0 부터 시작하고, ② i < N, j < M까지 진행합니다.

③ t[0]과 p[0]을 비교했을 때, 같지 않으므로 if절을 수행합니다. i ← i-j, j ← -1에 의하여 i=0, j=-1이 됩니다.

④ 루프를 한 바퀴 돌았으니 i++, j++를 해 주어 i=1, j=0이 됩니다.

그렇다면 현재 상태는 다음과 같습니다.

이렇게 루프를 돌면서 하나 하나 텍스트와 패턴을 대조해가다 보면 "cute"를 만나게 되겠죠? 확인해 보겠습니다.

③ t[13]과 p[0]을 비교하게 되는데, 같으므로 if절을 수행하지 않습니다.

④ 루프를 돌았으니 i++, j++를 해 주면 i=14, j=1이 됩니다.

이렇게 루프를 계속 진행하면 텍스트와 패턴이 cute의 마지막인 e까지 똑같다는 것이 확인됩니다.

 

이 때 i=16, j=3인 상태이고, 루프가 끝날 때 i++, j++를 해 주면 i=17, j=4가 되는데,

j < M(=4) 까지 루프를 도는 것이었으니 for문을 탈출합니다.

⑤ 탈출한 뒤 if절의 조건인 j=M 을 만족하므로 i-M = 13을 리턴하며 함수를 끝냅니다.

이렇게 되면 최종 리턴 값은 13이 되고, 이는 cute가 있는 위치를 가리킨다는 걸 알 수 있습니다.

 

이처럼 한 글자씩 무식하게 비교하는 알고리즘을 직선적 알고리즘이라 하며,

방금의 예시를 보았듯 찾으려는 패턴이 텍스트의 맨 끝에 있거나, 아예 없을 경우 처음부터 끝까지 패턴을 비교해야 하므로 시간 복잡도는 최악의 경우 O(MN) 까지 올라갑니다.

 

이런 식으로 웹페이지에서 탐색을 하면 무지막지한 시간이 걸리겠죠? 상상만 해도 답답합니다.

다음 시간에는 패턴에서 어떠한 정보를 미리 구하여 스트링 탐색을 껑충껑충 할 수 있는 KMP 알고리즘에 대해 알아보겠습니다.

 

<틀린 점이 있다면 지적 부탁드립니다. 감사합니다.>