1. Brute Force Text Search ( n*n 비효휼적 )
#include <stdio.h>
#include <string.h>
#define OUTPUT(x) printf("index:%2d\n",(x))
void BF(char *src, int len_src, char *dest, int len_dest)
{
int i, j;
for( i = 0; i <= len_dest - len_src; ++i )
{
for( j = 0; j < len_src && src[j] == dest[i+j]; ++j )
;
if( j >= len_src )
OUTPUT(i);
}
}
int main()
{
char str[] = "acgagggaggputer";
char search_str[] = "gagggagg";
BF( search_str, strlen(search_str), str, strlen(str) );
return 0;
}
2. Karp-Rabin Text Search
// 각자리의 아스키 코드에 2^0 2^1, 2^3.. 을 곱해서 해쉬값을 만들어 낸다.
hx = (hx<<1) + src[i];
hy = (hy<<1) + dest[i];
// 십진시프트를 이용한 거랑 비슷하다.
// itoa의 방식
// Sum = Sum*10 + a[i] - '0'
// 맨앞의 값만 삭제하고 다른 자리에는 2만 곱해주면 자릿수가 변경된다.
// 처음) h*2^4 + e*2^3 + l*2^2 + l*2^1 + o*2^0
// 다음) e*2^4 + l*2^3 + l*2^2 + o*2^1 + w*2^0
hy = ((hy - dest[i]*d)<<1) + dest[i+len_src];
#include <stdio.h>
#include <string.h>
#define OUTPUT(x) printf("index:%2d\n",(x))
void KR(char *src, int len_src, char *dest, int len_dest)
{
int d, hx, hy, i;
for( d=i=1; i < len_src; i++ )
d <<= 1;
for( hy = hx = i =0; i < len_src; i++ )
{
hx = (hx<<1) + src[i];
hy = (hy<<1) + dest[i];
}
for( i = 0; i < len_dest-len_src; i++ )
{
if( hx == hy && memcmp(src, dest+i, len_src) == 0)
OUTPUT(i);
hy = ((hy - dest[i]*d)<<1) + dest[i+len_src];
}
}
int main()
{
char str[] = "acgagggaggputer";
char search_str[] = "gagggagg";
KR( search_str, strlen(search_str), str, strlen(str) );
return 0;
}
3. Shift Or Text Search
- 미리 배열속에 시프트 연산을 해놓는다. PreSo( 비트별로 Or를 취해서 0이 나오면 찾는방식 )
#include <stdio.h>
#include <string.h>
#define ASIZE 256 #define OUTPUT(x) printf("index:%2d\n",(x))
int preSo(char *x, int m, unsigned int S[])
{
unsigned int j, lim;
int i;
for (i = 0; i < ASIZE; ++i)
S[i] = ~0;
for (lim = i = 0, j = 1; i < m; ++i, j <<= 1)
{
S[x[i]] &= ~j;
lim |= j;
}
lim = ~(lim>>1);
return(lim);
}
void SO(char *src, int len_src, char *dest, int len_dest)
{
unsigned int lim, state;
unsigned int S[ASIZE];
int j;
lim = preSo(src, len_src, S); // lim = 111111100
for (state = ~0, j = 0; j < len_dest; ++j)
{
state = (state<<1) | S[dest[j]];
if (state < lim)
OUTPUT(j - len_src + 1);
}
}
int main()
{
char str[] = "acagaggaggacttcact";
char search_str[] = "gagg";
SO( search_str, strlen(search_str), str, strlen(str) );
return 0;
}
4. Morris_Pratt Text Search
1) 대상 문자열이 "
sesesesesehero" , 찾고자 하는 문자열 "
sesehero" 일때 대상문자열 인덱스가 4이면 's' 인데 'h' 랑 비교했을때 틀리므로 비교를 다시 시작한다. 이때 접두, 접미를 이용하게 되는데
찾고자 하는 문자열 인덱스가 2이면 's' 인데 's'랑 다시 비교한다.
2) 결국 처음부터 다시 비교해야 하는 비용 '2'를 아끼게 된 꼴이 되므로 효율적이다.
#include <stdio.h>
void preMp( char* src, int len_src, int mpNext[] )
{
int i, j;
i = 0;
j = mpNext[0] = -1;
// 반복되는 문자를 찾아서 인덱스를 만들어준다.
while( i < len_src )
{
while( j > -1 && src[i] != src[j] )
j = mpNext[j];
mpNext[++i] = ++j;
}
}
void MP( char* src, int len_src, char* dest, int len_dest )
{
int i, j, mpNext[20];
preMp( src, len_src, mpNext );
i = j = 0;
while( j < len_dest )
{
// sesese를 만났을때 se~이후부터 비교를 시작한다.
while( i > -1 && src[i] != dest[j] )
i = mpNext[i];
++i;
++j;
if( i >= len_src )
{
printf( "%d\n", j - i );
i = mpNext[i];
}
}
}
int main()
{
char y[] = "sesesesesehero";
char x[] = "sesehero";
MP( x, strlen(x), y, strlen(y) );
return 0;
}
5. Knuth_Morris_Pratt Text Search
1) Morris_Pratt 알고리즘에서 PreMp 만 수정한 알고리즘. ( Knuth 할아버지.. )
- 핵심은 접두를 접미로 밀어봐도 틀린 값이라면 틀린만큼 더 밀어준다는 개념이다.
- 틀린 값의 비교를 절약하므로 Morris 보다도 효율적이다.
void preKmp( char *src, int len_src, int mpNext[] )
{
int i, j;
i = 0;
j = mpNext[0] = -1;
while (i < len_src)
{
while (j > -1 && src[i] != src[j])
j = mpNext[j];
i++;
j++;
if (src[i] == src[j])
mpNext[i] = mpNext[j];
else
mpNext[i] = j;
}
}
6. Boyer - Moore Text Search
1) 뒤에서 부터 비교후, 틀리다면 A와 맞는곳으로 이동
2) C와 비교후 틀리다면 C까지 땡겨서 비교한다. 그후에, 끝이 G이므로 G가 나올때까지 땡긴다.
#include <stdio.h>
#define OUTPUT(x) printf("index:%2d\n",(x))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define ASIZE 256
#define XSIZE 256
void preBmBc(char *src, int len_src, int bmBc[])
{
int i;
for (i = 0; i < ASIZE; ++i)
bmBc[i] = len_src;
for (i = 0; i < len_src - 1; ++i)
bmBc[src[i]] = len_src - i - 1;
}
void suffixes(char *src, int len_src, int *suff)
{
int f, g, i;
suff[len_src - 1] = len_src;
g = len_src - 1;
for (i = len_src - 2; i >= 0; --i)
{
if (i > g && suff[i + len_src - 1 - f] < i - g)
suff[i] = suff[i + len_src - 1 - f];
else
{
if (i < g)
g = i;
f = i;
while (g >= 0 && src[g] == src[g + len_src - 1 - f])
--g;
suff[i] = f - g;
}
}
}
void preBmGs(char *src, int len_src, int bmGs[])
{
int i, j, suff[XSIZE];
suffixes(src, len_src, suff);
for (i = 0; i < len_src; ++i)
bmGs[i] = len_src;
j = 0;
for (i = len_src - 1; i >= 0; --i)
if (suff[i] == i + 1)
for (; j < len_src - 1 - i; ++j)
if (bmGs[j] == len_src)
bmGs[j] = len_src - 1 - i;
for (i = 0; i <= len_src - 2; ++i)
bmGs[len_src - 1 - suff[i]] = len_src - 1 - i;
}
void BM(char *src, int len_src, char *dest, int len_dest)
{
int i, j, bmGs[XSIZE], bmBc[ASIZE];
/* Preprocessing */
preBmGs(src, len_src, bmGs);
preBmBc(src, len_src, bmBc);
/* Searching */
j = 0;
while (j <= len_dest - len_src)
{
for (i = len_src - 1; i >= 0 && src[i] == dest[i + j]; --i);
if (i < 0)
{
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[dest[i + j]] - len_src + 1 + i);
}
}
int main()
{
char y[] = "seseserahero";
char x[] = "seserahero";
BM( x, strlen(x), y, strlen(y) );
return 0;
}
- 드라이버는 하나가 있어도 되지만 실제 장치가 2개이상이 있다면 각 장치마다의 상태를 따로 관리해야 한다.
WINOBJ.EXE
