- 技术
- BM算法
#ifndef __BM_H__
#define __BM_H__
#include <algorithm>
using namespace std
;
#define ASIZE 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
[m
+ 1];
suffixes(x
, m
, suff
);
for (i
= 0; i
< m
; ++i
)
bmGs
[i
] = m
;
j
= 0;
for (i
= m
- 1; i
>= 0; --i
)
if (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
;
}
bool BM(char *y
, int n
, char *x
, int m
) {
int i
, j
, bmGs
[m
+ 1], bmBc
[ASIZE
];
preBmGs(x
, m
, bmGs
);
preBmBc(x
, m
, bmBc
);
j
= 0;
while (j
<= n
- m
) {
for (i
= m
- 1; i
>= 0 && x
[i
] == y
[i
+ j
]; --i
);
if (i
< 0) return true;
else
j
+= max(bmGs
[i
], bmBc
[y
[i
+ j
]] - m
+ 1 + i
);
}
return false;
}
#endif
参考资料
Boyer-Moore algorithm
Processed:
0.010, SQL:
9
