su  1.13.17
Typedefs | Functions
Fast string searching with Boyer-Moore algorithm

The Boyer-Moore algorithm is used to implement fast substring search. More...

Typedefs

typedef struct bw_fwd_table bm_fwd_table_t
 Forward skip table for Boyer-Moore algorithm.
 

Functions

bm_fwd_table_tbm_memmem_study (char const *needle, size_t nlen)
 Build case-sensitive forward skip table bm_fwd_table_t for Boyer-Moore algorithm.
 
char * bm_memmem (char const *haystack, size_t hlen, char const *needle, size_t nlen, bm_fwd_table_t *fwd)
 Search for a substring using Boyer-Moore algorithm.
 
bm_fwd_table_tbm_memcasemem_study (char const *needle, size_t nlen)
 Build case-insensitive forward skip table for Boyer-Moore algorithm.
 
char * bm_memcasemem (char const *haystack, size_t hlen, char const *needle, size_t nlen, bm_fwd_table_t *fwd)
 Search for substring using Boyer-Moore algorithm.
 

Detailed Description

The Boyer-Moore algorithm is used to implement fast substring search.

The algorithm has some overhead caused by filling a table. Substring search then requires at most 1 / substring-length less string comparisons. On modern desktop hardware, Boyer-Moore algorithm is seldom faster than the naive implementation if the searched substring is shorter than the cache line.


Sofia-SIP 1.13.17 - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.