C语言字符串匹配函数建议收藏

 1 #include <stdio.h>  2 #include <stdlib.h>  3 #include <string.h>  4 #include <assert.h>  5 #include <time.h>  6  7 /*  8 pattern:  9 pos:  10 */  11  12 static int badShift[256];  13  14  15 static int goodPostfixLastPos(const char *pattern,int pos)  16 {  17 #define _break(flag) if(flag){ break;}  18  19 int flag = 0;  20 int len = strlen(pattern);  21 int postFix_len = len - pos;  22 int postFix_position = pos;  23 int initStart = pos - postFix_len;  24 int last_start = 0;  25 while(postFix_len)  26  {  27 last_start = (postFix_position == pos) ?initStart:0;  28 int postFix_start = postFix_position;  29 for(;last_start>=0 && postFix_start<len;last_start++,postFix_start++)  30  {  31 flag = (pattern[last_start] == pattern[postFix_start]);  32 _break(!flag);  33  34  }  35  36  _break(flag);  37 if(initStart >= 0)  38  {  39 initStart--;  40  }  41 else  42  {  43 postFix_position++;  44 postFix_len--;  45  }  46  }  47  48 return flag?last_start-1:-1;  49 }  50  51 static int *calc_goodPostfixShift(const char *pattern,int *goodShift)  52 {  53 int len = strlen(pattern);  54 for(int i=0;i<len;i++)  55  {  56 goodShift[i] = len - goodPostfixLastPos(pattern,i) - 1;  57  }  58  59 return goodShift;  60 }  61  62 static int *clac_badcharShift(const char *ptrn)  63 {  64 int i;  65 int pLen = strlen(ptrn);  66  67 for(i = 0; i < 256; i++)  68  {  69 *(badShift+i) = pLen;  70  }  71  72 while(pLen != 0)  73  {  74 *(badShift+(unsigned char)*ptrn++) = --pLen;  75  }  76  77 return badShift;  78 }  79  80 int BMSearch(const char *str,const char *pattern)  81 {  82  83 int goodShift[strlen(pattern)];  84 int len1 = strlen(str);  85 int len2 = strlen(pattern);  86  87  clac_badcharShift(pattern);  88  calc_goodPostfixShift(pattern,goodShift);  89 for(int i=len2 - 1;i<len1;)  90  {  91 int start = i;  92 int pos_pattern = len2 - 1;  93 for(;pos_pattern>=0;pos_pattern--,start--)  94  {  95 if(str[start] != pattern[pos_pattern])  96  {  97 break;  98  }  99  } 100 if(pos_pattern < 0) 101  { 102 return start + 1; 103  } 104 105 if(pos_pattern == (len2 - 1)) 106  { 107 i += badShift[str[start]]; 108  } 109 else 110  { 111 i += goodShift[pos_pattern + 1]; 112  } 113  } 114 115 return -1; 116 }