Boyer-Moore의 탐색 알고리즘/보이어무어

int BM_Search(char *p, char *a)

{

int i, j, t, M, N;



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

InitSkip(p); /* skip[] 초기화 */



for(i = j = M - 1; j >= 0; i--, j--)

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

{

t = skip[index(a[i])];

i = i + max(M-j, t); /* 둘중 큰것 선택 */

if(i >= N) return(N); /* 매칭안됨 */

j = M - 1; /* p의 마지막 문자 위치 */

}

return(i+1); /* 일치된 문자열의 시작 위치 */

}

InitSkip(p) {

for(각 알파벳 문자 k에 대해) skip[k] = M; // 초기화

//보통은 (int k=0; k < 26; k++) skip[k] = M;

// p에 포함된 각 문자에 대해,

for(int j = 0; j < M; j++) skip[index(p[j])] = M-j-1;

}

index(char c) {

if(c가 소문자로 변경) return (c-'a');

else if(c가 대문자이면) return(c-'A');

}

 

skip[다른문자] = M = 5

skip['S'] = M-1 = 4

skip['T'] = M-2 = 3

skip['I'] = M-3 = 2

skip['N'] = M-4 = 1

skip['G'] = M-5 = 0