고지식한 패턴 검색
본문이 “ABCABACDC” 일 때, 찾고자 하는 문자열 패턴은 “BA”이다.
// 알고리즘 첫 번째 루틴
A B C A B A C D C
|
B A
// 알고리즘 두 번째 루틴
A B C A B A C D C
|
B A
A B C A B A C D C
| |
B A
...
// 일치하는 패턴을 찾음
A B C A B A C D C
| |
B A
C
•
어떠한 요령없이 패턴과 일치하는지 하나씩 비교하며 찾는 이 알고리즘을 고지식한 검색 (Naive Search) 또는 무식한 검색 (Brute Force Search) 라고 한다.
•
본문의 길이가 N이고, 패턴의 길이를 M 이라 할 때, 본문 속에 존재하는 패턴을 찾기 위해 최악의 경우 N*M 번의 비교를 수행해야한다.
구현
int BruteForce(char* Text, int TextSize, int Start,
char* Pattern, int PatternSize)
{
int i, j = 0;
for (i=Start; i <= TextSize - PatternSize; i++)
{
for (j=0; j<PatternSize; j++) // PatternSize 만큼 Pattern 을 순회하며 본문비교
{
if ( Text[i+j] != Pattern[j] ) // 본문과 패턴내의 문자열이 같지 않으면 break
break
}
if ( j >= PatternSize) // j 가 PatternSize 이상이면 일치하는 문자열을 찾음
return i; // 해당 인덱스 반환
}
return -1;
}
C
