[알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(1)

Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. 

 

↓그 전 KMP 알고리즘 관련 글

2021.07.23 - [Algorithm/Pattern Searching] - [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘)

 

 

이 알고리즘을 이 두 가지 접근법을 조합한 것입니다.

각각의 접근법에 대해 패턴을 처리하고,

검색을 수행할 때 두 접근법이 제안하는 값 중 최대값만큼 패턴을 이동합니다.

(두 가지 원리 모두 각각 독립적으로 사용해도 문자열 검색이 가능합니다.)

 

1) Bad Character
2) Good Suffix

 

 

이번 글에서는 Bad Character 원리부터 살펴보겠습니다. 

---

▶ Bad Character 원리

 

패턴의 현재 문자와 일치하지 않는 텍스트의 문자를 바로 "Bad Character" 라고 부릅니다.

이 원리는 두 가지 경우로 나뉘는데,

 

1) Bad Character가 패턴에 존재할 때

2) Bad Character가 패턴에 존재하지 않을 때

 

로 나뉩니다.

 

※ 이 알고리즘은 문자열 검색을 패턴의 맨 마지막 글자부터 시작합니다. 

 

1) Bad Character가 패턴에 존재할 때

 

 

Bad Character가 패턴에 존재할 경우

 

 

2) Bad Character가 패턴에 존재하지 않을 때

 

 

Bad Character가 패턴에 존재하지 않을 경우

 

이 알고리즘은 항상 2)의 경우가 나오는 최적의 경우, 항상 패턴을 m만큼 이동시키므로, 

시간복잡도는 O(n/m)입니다(n: 텍스트의 길이, m: 패턴의 길이). 

 

알고리즘 구성

 

 

- badchar[ ]

- txt[ ]

- pat[ ]

 

함수

- badCharHeuristic(string str, int size, int badchar[NO_OF_CHARS])

- search(string txt, string pat)

 

 

 

badCharHeuristic 함수

 

 

badCharHeuristic 함수

 

알고리즘 실행

 

 

s – 텍스트에서 패턴의 시작점 위치

j – 현재 비교하고 있는 패턴 인덱스

 

 

 

void search(string txt, string pat)
{
	int m = pat.size();
	int n = txt.size();

	int badchar[NO_OF_CHARS];


	badCharHeuristic(pat, m, badchar);

	int s = 0; 

	while (s <= (n - m))
	{
		int j = m - 1;


		while (j >= 0 && pat[j] == txt[s + j])
			j--;

		if (j < 0)
		{
			cout << "pattern occurs at shift = " << s << endl;

			s += (s + m < n) ? m - badchar[txt[s + m]] : 1;

		}

		else
			s += max(1, j - badchar[txt[s + j]]);
	}
}

 

 

 

 

Bad Character 원리는 최악의 경우, 시간복잡도가 O(mn) 입니다. 

→ 예를 들어, txt[] = "AAAAAAAAAAAAAAAAAAAAA" 이고, pat[] = "AAAAAA" 인 경우

 

 

전체 코드입니다. 

 

 

#include <iostream>

using namespace std;
#define NO_OF_CHARS 256


void badCharHeuristic(string str, int size,
	int badchar[NO_OF_CHARS])
{
	int i;


	for (i = 0; i < NO_OF_CHARS; i++)
		badchar[i] = -1;

	for (i = 0; i < size; i++)
		badchar[(int)str[i]] = i;
}

void search(string txt, string pat)
{
	int m = pat.size();
	int n = txt.size();

	int badchar[NO_OF_CHARS];


	badCharHeuristic(pat, m, badchar);

	int s = 0; 

	while (s <= (n - m))
	{
		int j = m - 1;


		while (j >= 0 && pat[j] == txt[s + j])
			j--;

		if (j < 0)
		{
			cout << "pattern occurs at shift = " << s << endl;

			s += (s + m < n) ? m - badchar[txt[s + m]] : 1;

		}

		else
			s += max(1, j - badchar[txt[s + j]]);
	}
}

int main()
{
	string txt = "ABAAABCD";
	string pat = "ABC";
	search(txt, pat);
	return 0;
}

 

 

수행 결과

pattern occurs at shift = 4

 

 

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