BM(3) BSD Programmer's Manual BM(3)
bm_comp, bm_exec, bm_free - Boyer-Moore string search
#include <sys/types.h>
#include <bm.h>
bm_pat *
bm_comp(const unsigned char *pattern, size_t patlen,
const unsigned char freq[256]);
unsigned char *
bm_exec(bm_pat *pdesc, unsigned char *text, size_t len);
void
bm_free(bm_pat *pdesc);
These routines implement an efficient mechanism to find an occurrence of
a byte string within another byte string.
bm_comp() evaluates patlen bytes starting at pattern and returns a
pointer to a structure describing them. The bytes referenced by pattern
may be of any value.
The search takes advantage of the frequency distribution of the bytes in
the text to be searched. If specified, freq should be an array of 256
values, with higher values indicating that the corresponding character
occurs more frequently. (A less than optimal frequency distribution can
only result in less than optimal performance, not incorrect results.) If
freq is NULL, a system default table is used.
bm_exec() returns a pointer to the leftmost occurrence of the string
given to bm_comp() within text, or NULL if none occurs. The number of
bytes in text must be specified by len.
Space allocated for the returned description is discarded by calling
bm_free() with the returned description as an argument.
The asymptotic speed of bm_exec() is O(len / patlen).
regexp(3), strstr(3)
Andrew Hume and Daniel Sunday, Software Practice and Experience, Fast
String Searching, Volume 21, 11 (November 1991), 1221-48.
MirOS BSD #10-current June 29, 1999 1
Generated on 2012-02-20 02:47:02 by $MirOS: src/scripts/roff2htm,v 1.70 2011/12/03 18:21:12 tg Exp $
These manual pages and other documentation are copyrighted by their respective writers;
their source is available at our CVSweb,
AnonCVS, and other mirrors. The rest is Copyright © 2002‒2011 The MirOS Project, Germany.
This product includes material
provided by Thorsten Glaser.
This manual page’s HTML representation is supposed to be valid XHTML/1.1; if not, please send a bug report – diffs preferred.