반응형
비트컴퓨터에서 과제로 제출했던 코드.
실제 동작테스트 완료된 자료입니다.
예제코드
#if 0
void preBmBc(char *x, int m, int bmBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff); // suffix 배열을 만든다.
for (i = 0; i < m; ++i)
bmGs[i] = m;
// good-suffix는 이동거리 정보를 갖게 되는데. 최대 이동거리는 문자열의
// 길이이므로 모든 배열의 요소를 strlen(m)으로 세팅
j = 0;
for (i = m - 1; i >= 0; --i)
// suffix 비교방식은 가장 뒤의 인덱스부터 비교하게 된다.
// m=8일 경우 7 6 5 4 3 2 1 순으로 비교
if (suff[i] == i + 1)
// 지금까지 확정된 문자열이 앞에 인덱스와 일치하는 경우!!
// 처음으로 틀린위치 전이 앞의 문자열과 완벽히 일치!!
// a b x x x x a b
for (; j < m - 1 - i; ++j)
// 뒤에서 부터 비교를 하기때문에..m - 1 - i는
// 즉.. 총 길이에서 확정된 길이 플러스 i+1만큼 옮기는게 가능.
// 단.. 나머지들은 비교를 하나마나 그만큼 옮기는게 가능하다?!
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
// 완전 같게 되는경우. 확정된 길이를 뺀만큼 옮기게 된다.
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
// suffix로 움직이지 못하는 경우가 발생하면..
// 즉 suffix[i]까지 왔지만 앞에 일치하는 접미사가 없어서 못움직이면..
// bmgs[최대 인덱스] 는 한값으로 1으로 수렴하게 된다.
// 어떤경우던지 suff[최대 인덱스는]는 m이 되기때문이다.
// 일치하는 접미사가 중간에 위치하는 경우..
// 그 접미사가 발견된 인덱스에 해당하는 gs 배열 세팅..
// 최대 이동거리가 아아니라.. 그보다 작아지게 된다.
// gs는.. 해당 인덱스 까지 비교한후.. suffix 배열의 정보.. 즉 앞에서 일치하게 되는 접미사 부분만큼 이동.
}
void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
#endif
#include
#include
#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 *x, int m, int bmBc[]) {
int i; for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; }
}
}
/*
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}*/
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff); // suffix 배열을 만든다.
for (i = 0; i < m; ++i)
bmGs[i] = m;
// good-suffix는 이동거리 정보를 갖게 되는데. 최대 이동거리는 문자열의
// 길이이므로 모든 배열의 요소를 strlen(m)으로 세팅
j = 0;
for (i = m - 1; i >= 0; --i)
// suffix 비교방식은 가장 뒤의 인덱스부터 비교하게 된다.
// m=8일 경우 7 6 5 4 3 2 1 순으로 비교
if (suff[i] == i + 1)
// 지금까지 확정된 문자열이 앞에 인덱스와 일치하는 경우!!
// 처음으로 틀린위치 전이 앞의 문자열과 완벽히 일치!!
// 일단 쭉~ 스캔하면서 완벽 일치의 경우만 뽑아본다.
// a b x x x x a b
for (; j < m - 1 - i; ++j)
// 뒤에서 부터 비교를 하기때문에..m - 1 - i는
// 즉.. 총 길이에서 확정된 길이 플러스 i+1만큼 옮기는게 가능.
// 단.. 나머지들은 비교를 하나마나 그만큼 옮기는게 가능하다?!
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
// 완전 같게 되는경우. 확정된 길이를 뺀만큼 옮기게 된다.
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
// suffix로 움직이지 못하는 경우가 발생하면..
// 즉 suffix[i]까지 왔지만 앞에 일치하는 접미사가 없어서 못움직이면..
// bmgs[최대 인덱스] 는 한값으로 1으로 수렴하게 된다.
// 어떤경우던지 suff[최대 인덱스는]는 m이 되기때문이다.
// 일치하는 접미사가 중간에 위치하는 경우..
// 그 접미사가 발견된 인덱스에 해당하는 gs 배열 세팅..
// 최대 이동거리가 아아니라.. 그보다 작아지게 된다.
// gs는.. 해당 인덱스 까지 비교한후.. suffix 배열의 정보.. 즉 앞에서 일치하게 되는 접미사 부분만큼 이동.
}
void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
int main()
{
char y[] = "acgagggaggputer";
char x[] = "gcagagag";
BM( x, strlen(x), y, strlen(y) );
return 0;
}
반응형