- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <assert.h>
- #include <time.h>
- /*
- pattern:
- pos:
- */
- static int badShift[256];
- static int goodPostfixLastPos(const char *pattern,int pos)
- {
- #define _break(flag) if(flag){ break;}
- int flag = 0;
- int len = strlen(pattern);
- int postFix_len = len - pos;
- int postFix_position = pos;
- int initStart = pos - postFix_len;
- int last_start = 0;
- while(postFix_len)
- {
- last_start = (postFix_position == pos) ?initStart:0;
- int postFix_start = postFix_position;
- for(;last_start>=0 && postFix_start<len;last_start++,postFix_start++)
- {
- flag = (pattern[last_start] == pattern[postFix_start]);
- _break(!flag);
- }
- _break(flag);
- if(initStart >= 0)
- {
- initStart--;
- }
- else
- {
- postFix_position++;
- postFix_len--;
- }
- }
- return flag?last_start-1:-1;
- }
- static int *calc_goodPostfixShift(const char *pattern,int *goodShift)
- {
- int len = strlen(pattern);
- for(int i=0;i<len;i++)
- {
- goodShift[i] = len - goodPostfixLastPos(pattern,i) - 1;
- }
- return goodShift;
- }
- static int *clac_badcharShift(const char *ptrn)
- {
- int i;
- int pLen = strlen(ptrn);
- for(i = 0; i < 256; i++)
- {
- *(badShift+i) = pLen;
- }
- while(pLen != 0)
- {
- *(badShift+(unsigned char)*ptrn++) = --pLen;
- }
- return badShift;
- }
- int BMSearch(const char *str,const char *pattern)
- {
- int goodShift[strlen(pattern)];
- int len1 = strlen(str);
- int len2 = strlen(pattern);
- clac_badcharShift(pattern);
- calc_goodPostfixShift(pattern,goodShift);
- for(int i=len2 - 1;i<len1;)
- {
- int start = i;
- int pos_pattern = len2 - 1;
- for(;pos_pattern>=0;pos_pattern--,start--)
- {
- if(str[start] != pattern[pos_pattern])
- {
- break;
- }
- }
- if(pos_pattern < 0)
- {
- return start + 1;
- }
- if(pos_pattern == (len2 - 1))
- {
- i += badShift[str[start]];
- }
- else
- {
- i += goodShift[pos_pattern + 1];
- }
- }
- return -1;
- }
- //该片段来自于http://www.codesnippet.cn/detail/230620149864.html
来源: http://www.codesnippet.cn/detail/230620149864.html