김효원, Swindler, coolx 님의 홈페이지

Programming

No.

504

Name.

swindler

Subject.

Brute Force Algorithm

Main Cate.

개발일반

Sub Cate.

Date.

2008-12-04 10:13

Hit.

3917 (210.182.190.136)

File.

brute.gif

bf.gif

// http://www-igm.univ-mlv.fr/~lecroq/string/

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

void bf( char *org, int n, char *sub, int m)
{
int i,j;
for( i=0; i<n-m+1; i++ )
{
for( j=0; j<m; j++ )
{
if( org[i+j] != sub[j] )
break;
}
if( j == m )
printf("%d\n", i );
}
}
int main()
{
char buff[] = "hello wowowr";
char sub[]="wow";

bf( buff, strlen(buff), sub, strlen(sub) );
return 0;
}

Brute Force Search 는 버퍼를 차례로 읽어가며 문자를 비교하는 알고리즘이다. 가장 기본적인 형태의 패턴매칭.
위 프로그램을 돌리면 결과 값은 6과 8이 나올것이다.

가장 기초적인 방법. text의 처음부터 끝까지 alphabet 하나씩 옮겨가며 비교. 따라서, TC 는 O( (n-m+1)m ) = O(nm) => O(n^2)

[바로가기 링크] : http://coolx.net/cboard/develop/504


[Modify] [Delete]		[Reply] [List]