/*
Simple implementation of the fast Boyer-Moore string search algorithm.
By X-Calibre, 2002
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *BoyerMoore( unsigned char *data, unsigned int dataLength, unsigned char *string, unsigned int strLength )
{
unsigned int skipTable[256], i;
unsigned char *search;
register unsigned char lastChar;
if (strLength == 0)
return NULL;
// Initialize skip lookup table
for (i = 0; i < 256; i++)
skipTable[i] = strLength;
search = string;
// Decrease strLength here to make it an index
i = --strLength;
do
{
skipTable[*search++] = i;
} while (i--);
lastChar = *--search;
// Start searching, position pointer at possible end of string.
search = data + strLength;
dataLength -= strLength+(strLength-1);
while ((int)dataLength > 0 )
{
unsigned int skip;
skip = skipTable[*search];
search += skip;
dataLength -= skip;
skip = skipTable[*search];
search += skip;
dataLength -= skip;
skip = skipTable[*search];
if (*search != lastChar) /*if (skip > 0)*/
{
// Character does not match, realign string and try again
search += skip;
dataLength -= skip;
continue;
}
// We had a match, we could be at the end of the string
i = strLength;
do
{
// Have we found the entire string?
if (i-- == 0)
return search;
} while (*--search == string[i]);
// Skip past the part of the string that we scanned already
search += (strLength - i + 1);
dataLength--;
}
// We reached the end of the data, and didn't find the string
return NULL;
}
int main(void)
{
static char data[] = "aaaabouaaa384982n chwercoiewar45u0943 twert3aaaaaaMarabou t9034u5t09t8493t43vkdsropgb";
static char search[] = "Marabou";
char *str = BoyerMoore( data, strlen(data), search, strlen(search) );
if (str == NULL)
puts( "String not found" );
else
puts( str );
return 0;
}
This page was generated by Syntax.cgi. Copyright © 2000, X-Calibre of Diamond Crew.
Contact us for a licensed version.