KMP/BM字符串匹配算法源码

#include "boyer_moore.h" #include <stdlib.h> #include <string.h> /************************************************************ * * Function: make_skip(char *, int) * * Purpose: Create a Boyer-Moore skip table for a given pattern * * Parameters: * ptrn => pattern * plen => length of the data in the pattern buffer * * Returns: * int * - the skip table * ***********************************************************/ int* make_skip(const char* ptrn, int plen) { int i; int* skip = (int*)malloc(256*sizeof(int)); memset(skip, 0, 256*sizeof(int)); for (i = 0; i < 256; i++) skip[i] = plen + 1; while (plen != 0) skip[(unsigned char)*ptrn++] = plen--; return skip; } /************************************************************ * * Function: make_shift(char *, int) * * Purpose: Create a Boyer-Moore shift table for a given pattern * * Parameters: * ptrn => pattern * plen => length of the data in the pattern buffer * * Returns: * int * - the shift table * ***********************************************************/ int* make_shift(const char* ptrn, int plen) { int* shift = (int*)malloc(plen*sizeof(int)); memset(shift, 0, plen*sizeof(int)); int* sptr = shift + plen - 1; const char* pptr = ptrn + plen -1; char c; c = ptrn[plen-1]; *sptr = 1; while (sptr-- != shift) { const char* p1 = ptrn + plen - 2, * p2, * p3; do { while (p1 >= ptrn && *p1-- != c) ; p2 = ptrn + plen - 2; p3 = p1; while (p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr) ; } while (p3 >= ptrn && p2 >= pptr); *sptr = shift + plen - sptr + p2 - p3; pptr--; } return shift; } /************************************************************ * * Function: bm_search(const char*, int, const char*, int, int*, int*) * * Purpose: Determines if a string contains a (non-regex) * substring. * * Parameters: * buf => data buffer we want to find the data in * blen => data buffer length * ptrn => pattern to find * plen => length of the data in the pattern buffer * skip => the B-M skip array * shift => the B-M shift array * * Returns: * -1 if not found or offset >= 0 if found * ***********************************************************/ int bm_search(const char* buf, int blen, const char* ptrn, int plen, int* skip, int* shift) { if (plen == 0) return -1; int b_idx = plen; while (b_idx <= blen) { int p_idx = plen, skip_stride, shift_stride; while (buf[--b_idx] == ptrn[--p_idx]) { if (p_idx == 0) return b_idx; } skip_stride = skip[(unsigned char)buf[b_idx]]; shift_stride = shift[p_idx]; b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride; } return -1; }