本文共 1965 字，大约阅读时间需要 6 分钟。

1、BF（暴力搜索）

匹配时间复杂度O(N*M)

主要过程：从原字符串开始搜索，若出现不能匹配，则从原搜索位置+1继续。

int bf(const char *text, const char *find)  {
         if (text == '/0' || find == '/0')          return -1;      int find_len = strlen(find);      int text_len = strlen(text);      if (text_len < find_len)          return -1;      char *s = text;      char *p = s;      char *q = find;      while (*p != '/0')      {
             if (*p == *q)          {
                 p++;              q++;          }          else          {
                 s++;              p = s;              q = find;          }          if (*q == '/0')          {
                 return (p - text) - (q - find);          }      }      return -1;  }

2、KR算法

KR算法是暴力算法的改进型。KR算法认为每次文本串与模式串比较的时候需要比较每一个字符，效率低。KR算法在每次比较时，用HASH算法计算文本串和模式串的HASH映射，通过比较映射值的大小来比较字符串是否匹配。但是考虑到HASH冲突，所以在映射值相同的时候，还需要近一步比较字符串是否相同。但是在每次比较时，需要计算HASH值，所以选择合适的HASH算法很重要。一般选择的算法为：HASH(x[0,1,2,......m-1]) = (x[0]*2^(m-1)+x[1]*2^(m-2)+......+x[m-1]*2^0) 对于模式串其HASH是不变的，而文本串每移动一个字符需重新计算。HASH(x[i+1,i+2,......i+m]) = (HASH(x[i,i+1,......i+m-1])-x[i]*2^(m-1))*2+x[i+m]

#define REHASH(x1, x2, m, h) ((((h)-((x1)<<((m)-1)))<<1) + (x2))void KRSearchPatternInText(const char* s, int m, const char* d, int n){
   int i;unsigned long hs = 0, hd = 0;for(i = 0; i < n; i++){
   hs = ((hs<<1) + (unsigned char)s[i]);hd = ((hd<<1) + (unsigned char)d[i]);}for(i = 0; i < m - n; ++i){
   if(hd == hs && memcmp(s+i, d, n) == 0)OUTPUT(i);hs = REHASH((unsigned char)s[i], (unsigned char)s[i+n], n, hs);}}

3、KMP算法

匹配时间复杂度：O(N)

主要过程：通过对字串进行预处理，当发现不能匹配时，可以不进行回溯。

int kmp(const char *text, const char *find)  {
         if (text == '/0' || find == '/0')          return -1;      int find_len = strlen(find);      int text_len = strlen(text);      if (text_len < find_len)          return -1;      int map[find_len];      memset(map, 0, find_len*sizeof(int));      //initial the kmp base array: map       map[0] = 0;      map[1] = 0;      int i = 2;      int j = 0;      for (i=2; i

转载地址：http://yzgwi.baihongyu.com/