brute force: 2개의 글

알고리즘(Algorithm) 실습10

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


 

10-1. 다음에 주어진 프로그램을 참고해서 주어진 Text string 자료에서Pattern을 모두 찾는 Boyer-Moore 의 알고리즘을 구현하고, 알고리즘 수행에서 문자비교회수를 헤아리고, Brute force, KMP 알고리즘의 성능과 비교하시오. 또한, 최악의 상태의 자료에 대해서도 실습하시오.

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

 

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

Pattern String : "STRING"

 

#include <iostream>

#include<stdlib.h>

#include<string>

using namespace std;

 

#define max(a,b) (((a)>(b))?(a):(b))

 

int *next; // KMP의next 테이블

int *lp; // BM의Lost Pos

 

int compare_cnt; // 비교회수카운터

 

 

int index(char c)

{

return toupper(c) - 'A'

}

 

void LastPos(char *p) // 불일치문자방책

{

int i, m = strlen(p);

 

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

{

compare_cnt++;

lp[i] = -1;

}

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

{

compare_cnt++;

lp[index(p[i])] = i;

}

}

 

 

 

void BoyerMoore(char *p, char *a)

{

int i, j, m = strlen(p), n = strlen(a);

compare_cnt = 0;

 

lp = new int[27]; // Lp[] 동적할당

LastPos(p);

 

j = 0;

 

while(j <= n-m)

{

compare_cnt++;

for(i=m-1; i>=0 && p[i]==a[j+i]; i--){compare_cnt++;};

if(i == -1)

{

cout << j << " "

j = j + m;

}

else

{

j = j + max(m-i, m-1-lp[index(a[j+i])]);

}

}

 

}

 

int brutesearch(char *p, char *a)

{

int i, j, m = strlen(p), n = strlen(a);

compare_cnt = 0;

 

for(i = 0, j = 0; j < m && i < n; i++, j++)

{

compare_cnt++;

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

{

compare_cnt++;

i -= j;

j = -1;

}

}

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

else return i;

}

 

void initnext(char *p) // next 테이블

{

int i, j, m = strlen(p);

next[0] = -1;

 

for(i=0,j=-1; i<m; i++, j++, next[i]=j)

{

compare_cnt++;

 

while(j>=0 && p[i]!=p[j])

{

compare_cnt++;

j = next[j];

}

}

}

 

int kmpsearch(char *p, char *a)

{

int i, j, m = strlen(p), n = strlen(a);

compare_cnt = 0;

next = new int[m+1];

initnext(p);

 

for(i=0, j=0; j<m && i<n; i++, j++)

{

compare_cnt++;

while(j>=0 && a[i]!=p[j]){

j = next[j];

compare_cnt++;

}

}

 

delete next;

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

else return i;

}

 

 

void main()

{

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

 

char w_Text[] = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

 

char w_Pattern[] = "AAAAAAAAAB"

 

cout << "Text : " << Text << "\n"

cout << "Pattern : " << Pattern << "\n\n"

 

cout << "[Brute Force] \nIndexPattern : " << brutesearch(Pattern, Text) << "\n"

cout << "Compare Count : " << compare_cnt << "\n\n"

 

cout << "[KMP] \nIndexPattern : " << kmpsearch(Pattern, Text) << "\n"

cout << "Compare Count : " << compare_cnt << "\n\n"

 

cout << "[Boyer Moore] \nIndexPattern : "

BoyerMoore(Pattern, Text);

cout << "\nCompare Count : " << compare_cnt << "\n\n"

 

cout << "\n\n\n"

 

cout << "Text : " << w_Text << "\n"

cout << "Pattern : " << w_Pattern << "\n\n"

 

cout << "[Brute Force] \nIndexPattern : " << brutesearch(w_Pattern, w_Text) << "\n"

cout << "Compare Count : " << compare_cnt << "\n\n"

 

cout << "[KMP] \nIndexPattern : " << kmpsearch(w_Pattern, w_Text) << "\n"

cout << "Compare Count : " << compare_cnt << "\n\n"

 

cout << "[Boyer Moore] \nIndexPattern : "

BoyerMoore(w_Pattern, w_Text);

cout << "\nCompare Count : " << compare_cnt << "\n\n"

 

}

 

 

 

 

 

 

▣ 결과 출력

 

 

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

알고리즘(Algorithm) 실습12  (0) 2010.02.15
알고리즘(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) 실습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