[Algorithm] - 문자열 검색 알고리즘 : Naive String Search

이론

문자열 검색 알고리즘이란,

어떤 문자열 S에서 패턴 P가 있는지 찾아내는 알고리즘이다.

 

Naive String Search 알고리즘은 문자열 검색 알고리즘 중에 효율이 좋지 않지만, 가장 구현하기 쉽고 작은 입력이라면 충분히 고려해볼만 한 알고리즘이다. 

 

전체 문자열 S의 길이를 N, 찾고자하는 패턴 P의 길이가 M이라고 할때,

 

최악의 경우 O((N-M)*M)의 시간 복잡도를 갖는다.

 

구현

전체적인 흐름은 아래와 같다.

1. 문자열 S의 첫번째 문자와 패턴 P의 첫번째 문자를 비교하여 같다면 다음 문자를 비교한다.

2-1 다음 문자가 같다면 그 다음 문자를 비교한다.

2-2 다음 문자가 같지 않다면,

      패턴 P를 한칸 밀어서 문자열 S의 두번째 문자와 패턴 P의 첫번째 문자를 비교한다.

3. 위와 같은 방식으로 문자열 S의 모든 부분을 탐색하고, 패턴 P를 발견한다면 종료한다.

 

코드

#include <iostream>
#include <string>

using namespace std;

bool naiveStringSearch(string s, string p /*Pattern*/)
{
	int n = s.size();
	int m = p.size();

	for(int i =0; i <= n-m; i++)
	{
		int count = 0;
		for(int j =0; j < m; j++)
		{
			cout << s[i+j] << " " << p[j] << "\n";
			if(s[i+j] == p[j])
			{
				count++;
			}
			else break;
		}
		if(count == m)
			return true;
	}

	return false;
}

int main()
{
	string s = "ayzabcde";
	string p = "abc";

	cout << "Pattern is Matched : " << boolalpha << naiveStringSearch(s,p) << "\n";
}

 

실행 결과

 

Github

GitHub - EGyeom/BlogMaker: this is Blog Maker