?? boyermoore.cpp
字號:
// BoyerMoore.cpp: implementation of the BoyerMoore class.
//
//////////////////////////////////////////////////////////////////////
#include "BoyerMoore.h"
#include <string.h>
//???
#define ASIZE 256
#define XSIZE 256
#define MAX(a, b) (a) > (b) ? (a) : (b)
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
BoyerMoore::BoyerMoore()
{}
BoyerMoore::~BoyerMoore()
{}
void BoyerMoore::test()
{
TimeIt tt;
BoyerMoore bm;
bm.search();
bm.OUTPUT(tt.GetMSecElapsed());
}
void BoyerMoore::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 BoyerMoore::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 BoyerMoore::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 BoyerMoore::search()
{
char *x = (char*)m_search,
*y = (char*)m_context;
int m = strlen(m_search),
n = strlen(m_context);
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);
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -