C Implementation of Boyer-Moore of BMH

Jeffrey Walton

Hi All, Anyone have c code for Boyer-Moore or BMH? I don't want to take the time to translate (and debug) pseudo code from my Algorithm Analysis textbook. I'd like to paste and compile. No wiki please. I already know their stuff is broken. How much crap can one site publish and claim it is fit for consumption? Jeff

David Crow

Jeffrey Walton wrote:

Anyone have c code for Boyer-Moore or BMH?

http://www-igm.univ-mlv.fr/~lecroq/string/node14.html[^] http://www-igm.univ-mlv.fr/~lecroq/string/node18.html[^] http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/boyerMoore.htm[^] http://www.dcc.uchile.cl/~rbaeza/handbook/algs/7/713.preproc.c[^]

Jeffrey Walton wrote:

No wiki please. I already know their stuff is broken.

Specfically what?

"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown

"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons

Jeffrey Walton

Hi David,

DavidCrow wrote:

http://www-igm.univ-mlv.fr/~lecroq/string/node14.html\[^\]

I ran across these. Unfortunately, some assembly is required and there are no instruction on calling 'void* p = Find(needle, haystack)'. Perhaps I am asking for too much.

DavidCrow wrote:

Specfically what?

Run it: Wiki's Boyer-Moore Horspool[^] implementation. Here's one of the best examples. A fellow claimed Dr. Adler's ADLER-32 reference implementation was wrong because it did not agree with wiki: Need peer review: May have found mistake in Adler-32![^]. Jeff

Joe Woodbury

This is from my bag-o-tricks library, but it's been a long time since I've tested or used them.

const char* CBTextSearch(const char* pSearchStr, const char* pStr, int textLen)
{
if (!pSearchStr || !*pSearchStr)
return pStr;

if (!pStr || !\*pStr)
	return NULL;

if (textLen < 0)
	textLen = (int)strlen(pStr);

int searchStrLen = (int)strlen(pSearchStr);

// Setup m\_skip table
int pSkipTable\[256\];

int i;
for (i = 0; i < 256; i++)
	pSkipTable\[i\] = searchStrLen;

for (i = 0; pSearchStr\[i\]; i++)
	pSkipTable\[(BYTE)pSearchStr\[i\]\] = searchStrLen - 1 - i;

register int right = searchStrLen - 1;
while (right < textLen)
{
	int j;
	for (j = searchStrLen - 1, i = right; j >= 0 && pSearchStr\[j\] == pStr\[i\]; j--)
		i--;

	if (j == -1)
		return &pStr\[i + 1\];

	right = max(i + pSkipTable\[(BYTE)pStr\[i\]\], right + 1);
}
return NULL;

}

const wchar_t* CBTextSearch(const wchar_t* pSearchStr, const wchar_t* pStr, int textLen)
{
if (!pSearchStr || !*pSearchStr)
return pStr;

if (!pStr || !\*pStr)
	return NULL;

if (textLen < 0)
	textLen = (int)wcslen(pStr);

int searchStrLen = (int)wcslen(pSearchStr);

// Setup m\_skip table
int\* pSkipTable = (int\*) \_alloca(searchStrLen \* sizeof(int));

int i;
for (i = 0; i < searchStrLen; i++)
	pSkipTable\[i\] = searchStrLen - 1 - i;

register int right = searchStrLen - 1;
while (right < textLen)
{
	int j;
	for (j = searchStrLen - 1, i = right; j >= 0 && pSearchStr\[j\] == pStr\[i\]; j--)
		i--;

	if (j == -1)
		return &pStr\[i + 1\];

	for (j = searchStrLen - 1; j >= 0; j--)
	{
		if (pSearchStr\[j\] == pStr\[i\])
		{
			right = max(i + pSkipTable\[j\], right + 1);
			break;
		}
	}
	if (j < 0)
		right = max(i + searchStrLen, right + 1);
}
return NULL;

}

Anyone who thinks he has a better idea of what's good for people than people do is a swine. - P.J. O'Rourke

Jeffrey Walton

Hi Joe, That was it. I did modify a bit to get a compile under boring old 'C': pSkipTable[(unsigned)pSearchStr[i]] Thanks. Jeff