search algorithm: 1개의 글

알고리즘(Algorithm) 실습8

Posted by Patchman
2010.02.15 15:36 Univ Study/알고리즘과 실습

 

8-1. 다음에 주어진 프로그램을 참고해서 주어진 Text string 자료에서Pattern을 모두 찾는 2가지 알고리즘(Brute force, Rabin-Karp)을 구현하고, 주어진 자료에 대해서 각 알고리즘이 수행한 문자비교 회수와 비교표를 출력하시오. 또한, 최악의 상태의 자료에 대해서도 실습하시오.

(예: a[]="AAAAAAAAAAAA", p[]="AAAAAAB")

 

Text String : "A TEXT STRING SEARCHING EXAMPLE CONSISTING OF A GIVEN STRING"

Pattern String : "STRING"

 

 

#include <iostream>

#include<stdlib.h>

using namespace std;

 

int comp = 0; // 비교연산카운터변수

 

int brutesearch(char *p, char *a)

{

int i, j, k, s = 0;

int M = strlen(p), N = strlen(a);

 

cout << a << "\n"

 

for(i=0, j=0; j<M && i<N; i++, j++)

{

comp++;

 

if(a[i] != p[j])

{

comp++;

 

cout << p << "\n"

 

// 비교표를출력하기위한반복문

for(k=0; k<=s; k++)cout << " ";

s++;

 

i -= j; // Text 는한칸씩이동한다

j= -1; // Pattern 은항상처음부터비교한다

}

 

}

cout << endl;

if(j == M) return i-M;

else return i;

}

 

const int q = 33554393; // 해시함수에의해결정되는값, 통상소수를선택함

const int d = 21; // 알파벳크기

 

int index(char c)

{

return toupper(c) - 'A'

}

 

int rksearch(char *p, char *a)

{

int i, dM = 1, h1 = 0, h2 = 0;

 

int M = strlen(p), N = strlen(a);

 

for(i=1; i<M; i++) dM = (d*dM) %q;

for(i=0; i<M; i++)

{

h1 = (h1 * d + index(p[i])) % q; // Pattern의Hash value

h2 = (h2 * d + index(a[i])) % q; // Text의Hash value

}

 

for(i=0; h1!=h2; i++) // Hash value가같지않다면비교한다.

{

comp++;

h2 = (h1 + d * q - index(a[i]) * dM) % q;

h2 = (h2 * d + index(a[i+M])) % q;

 

if(i > N-M) return N;

}

return i;

}

 

 

void result(int index)

{

cout << "Comparison : " << comp << "\n"

cout << "indexPattern : " << index << "\n\n\n"

comp = 0;

}

 

 

void main()

{

char Text1[] = "A TEXT STRING SEARCHING EXAMPLE CONSISTING OF A GIVEN STRING"

char Pattern1[] = "STRING"

 

char Text2[] = "AAAAAAAAAAAAAAAAAAAAAAAA"

char Pattern2[] = "AAAAAAAAAB"

 

 

int indexPattern = brutesearch(Pattern1, Text1);

result(indexPattern);

 

indexPattern = brutesearch(Pattern2, Text2);

result(indexPattern);

 

indexPattern = rksearch(Pattern1, Text1);

result(indexPattern);

 

indexPattern = rksearch(Pattern2, Text2);

result(indexPattern);

}

 

 



▣ 결과 출력



[Brute force]

 





[Rabin-Karp]

 

 

'Univ Study > 알고리즘과 실습' 카테고리의 다른 글

알고리즘(Algorithm) 실습11  (0) 2010.02.15
알고리즘(Algorithm) 실습10  (0) 2010.02.15
알고리즘(Algorithm) 실습8  (0) 2010.02.15
알고리즘(Algorithm) 실습7  (0) 2010.02.15
알고리즘(Algorithm) 실습6  (0) 2010.02.15
알고리즘(Algorithm) 실습5  (0) 2010.02.15