boyer moore: 1개의 글

알고리즘(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