字符串匹配算法总结

aabsee sds 模式串 ees
   ees

aabsees ds 模式串 ees
    ees

/*
* Sunday - 字符串匹配算法 -- 一种优于 KMP 的算法
* 思想类似于 BM 算法，只不过是从左向右匹配
* 遇到不匹配的看大串中匹配范围之外的右侧第一个字符在小串中的最右位置
* 另外：采用 BM/KMP 的预处理的做法，事先计算好移动步长 ，等到遇到不匹配的值直接使用
*/

#include <string.h>
#include <iostream>

using namespace std;

// 一个字符 8 位 最大 256 种
#define MAX_CHAR_SIZE 256

/* 设定每个字符最右移动步长，保存每个字符的移动步长
* 如果大串中匹配字符的右侧一个字符没在子串中，大串移动步长 = 整个串的距离 + 1
* 如果大串中匹配范围内的右侧一个字符在子串中，大串移动距离 = 子串长度 - 这个字符在子串中的位置
*/
int *setCharStep(char *subStr) {
   int *charStep  = new int[MAX_CHAR_SIZE];
   int  subStrLen = strlen(subStr);
   for(int i = 0; i < MAX_CHAR_SIZE; i++) charStep[i] = subStrLen + 1;

   // 从左向右扫描一遍 保存子串中每个字符所需移动步长
   for(int i = 0; i < subStrLen; i++) { charStep[(unsigned char)subStr[i]] = subStrLen - i; }
   return charStep;
}
/*
* 算法核心思想，从左向右匹配，遇到不匹配的看大串中匹配范围之外的右侧第一个字符在小串中的最右位置
* 根据事先计算好的移动步长移动大串指针，直到匹配
*/

int sundaySearch(char *mainStr, char *subStr, int *charStep) {
   int mainStrLen = strlen(mainStr);
   int subStrLen  = strlen(subStr);
   int main_i     = 0;
   int sub_j      = 0;

   while(main_i < mainStrLen) {
      // 保存大串每次开始匹配的起始位置，便于移动指针
      int tem = main_i;
      while(sub_j < subStrLen) {
            if(mainStr[main_i] == subStr[sub_j]) {
               main_i++;
               sub_j++;
               continue;
            }else {
               // 如果匹配范围外已经找不到右侧第一个字符，则匹配失败
               if(tem + subStrLen > mainStrLen) return -1;
               // 否则 移动步长 重新匹配
               char firstRightChar = mainStr[tem + subStrLen];
               main_i = tem + charStep[(unsigned char)firstRightChar];
               sub_j = 0;
               break;    // 退出本次失败匹配 重新一轮匹配
            }
      }
      if(sub_j == subStrLen) return main_i - subStrLen;
   }
   return -1;
}
int main(){
   char *mainStr = "absaddsasfasdfasdf";
   char *subStr = "dd";
   int *charStep = setCharStep(subStr);
   cout << "位置："<<sund  a y Search(mainStr,subStr  ,chart  ep)<< end l;
   system("pause");
   return 0;
}

void preQsBc(char *x, int m, int qsBc[]) {
   int i;

   for (i = 0; i < ASIZE; ++i)
      qsBc[i] = m + 1;
   for (i = 0; i < m; ++i)
      qsBc[x[i]] = m - i;
}


void QS(char *x, int m, char *y, int n) {
   int j, qsBc[ASIZE];

   /* Preprocessing */
   preQsBc(x, m, qsBc);

   /* Searching */
   j = 0;
   while (j <= n - m) {
      if (memcmp(x, y + j, m) == 0)
         OUTPUT(j);
      j += qsBc[y[j + m]];               /* shift */
   }
}

/* Sunday.h */
class Sunday
{
public:
   Sunday();
   ~Sunday();

public:
   int find(const char* pattern, const char* text);

private:
   void preCompute(const char* pattern);

private:
   //Let's assume all characters are all ASCII
   static const int ASSIZE = 128;
   int _td[ASSIZE] ;
   int _patLength;
   int _textLength;
};

/* Sunday.cpp */

Sunday::Sunday()
{
}

Sunday::~Sunday()
{
}

void Sunday::preCompute(const char* pattern)
{
   for(int i = 0; i < ASSIZE; i++)
      _td[i] = _patLength + 1;

   const char* p;
   for (p = pattern; *p; p++)
      _td[*p] = _patLength - (p - pattern);
}

int Sunday::find(const char* pattern, const char* text)
{
   _patLength = strlen(pattern);
   _textLength = strlen(text);

   if (_patLength <= 0 || _textLength <= 0)
      return -1;

   preCompute(pattern);

   const char *t, *p, *tx = text;

   while (tx + _patLength <= text + _textLength)
   {
      for (p = pattern, t = tx; *p; ++p, ++t)
      {
            if (*p != *t)
               break;
      }
      if (*p == 0)
            return tx-text;
      tx += _td[tx[_patLength]];
   }
   return -1;
}

int main()

{
   char* text = "blog.csdn,blog.net";
   char* pattern = "csdn,blog"    ;
   Sunday sunday;

   printf("The First Occurence at: %d/n",sunday.find(pattern,text));

   return 1;
}

// 下面是 Microsoft 的实现
// 经典算法
// 比 KMP 算法简单, 没有 KMP 算法高效
char * __cdecl strstr (
      const char * str1,
      const char * str2
      )
{
      char *cp = (char *) str1;
      char *s1, *s2;
      if (!*str2)
            return((char *)str1);
      while (*cp)
      {
               s1 = cp;
               s2 = (char *) str2;
               while (*s1 && *s2 && !(*s1-*s2) )
                        s1++, s2++;
               if (!*s2)
                        return(cp);
               cp++;
      }
      return(NULL);
}

unzip testStrstr.zip
cd testStrstr
make test