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_t * | bm_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_t * | bm_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. | |
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.
