########################################
字符串匹配算法总结
########################################

.. admonition:: 注

   本文转载自 https://blog.csdn.net/WINCOL/article/details/4795369

我想说一句 “我日，我讨厌 KMP！”。

KMP 虽然经典，但是理解起来极其复杂，好不容易理解好了，便起码来巨麻烦！

老子就是今天图书馆在写了几个小时才勉强写了一个有 bug 的、效率不高的 KMP，特别是计算 next 数组的部分。

其实，比 KMP 算法速度快的算法大把大把，而且理解起来更简单，为何非要抓住 KMP 呢？笔试出现字符串模式匹配时直接上 sunday 算法，既简单又高效，何乐而不为？

说实话，想到 sunday 算法的那个人，绝对是发散思维，绝对牛。当我在被 KMP 折磨的够呛的时候，我就琢磨，有没有别的好算法呢？？琢磨了半天也没想出个所以然来。笨啊，脑子不够发散。

下面贴上一位兄弟写的算法总结，很简单（建议 KMP 部分就不用看了，看了费脑子）。
参见：http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html

趁着做 Presentation 的功夫，顺便做一个总结

字符串匹配:
   在匹配串中寻找模式串是否出现，注意和最长公共子序列相区别 :abbr:`LCS (Longest Common Substring)`

Brute Force
****************************************

BF 或蛮力搜索算法

这是世界上最简单的算法了。

首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。

速度最慢。

那么，怎么改进呢？

我们注意到 Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？

当然是可以的。

我们也注意到，Brute Force 是很不 intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^

注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。

KMP 算法
****************************************

首先介绍的就是 KMP 算法。

原始论文：Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.

这个算法实在是太有名了，大学上的算法课程除了最笨的 Brute Force 算法，然后就介绍了 KMP 算法。也难怪，呵呵。谁让 Knuth D.E. 这么 world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的 Bible <The Art of Computer Programming>( 业内人士一般简称 TAOCP). 稍稍提一下，有个叫 H.A.Simon 的家伙，不仅拿了 Turing Award ，顺手拿了个 Nobel Economics Award ，做了 AI 的爸爸，还是 Chicago Univ 的 Politics PhD ，可谓全才。

KMP 的思想是这样的:
   利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离

   比如模式串 ababac 这个时候我们发现在 c 处不匹配，然后我们看 c 前面那串字符串的最大相等前后缀，然后再来移动

   下面的两个都是模式串，没有写出来匹配串

   原始位置 ab **aba** c

   移动之后 **aba** bac

   因为后缀是已经匹配了的，而前缀和后缀是相等的，所以直接把前缀移动到原来后缀处，再从原来的 c 处，也就是现在的第二个 b 处进行比较。 这就是 KMP 。

Horspool 算法
****************************************

当然，有市场就有竞争，字符串匹配这么大一个市场，不可能让 BF 和 KMP 全部占了，于是又出现了几个强劲的对手。

第一个登场的是

论文：Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506

Horspool 算法的思想很简单的。不过有个创新之处就是模式串是从右向左进行比较的。很好很强大，为后来的算法影响很大。

匹配串： **abcbc** sdxzcxx

模式串： **cbcac**

这个时候我们从右向左进行对暗号，c-c ，恩对上了，第二个 b-a ，不对啊，我们应该怎么办？难道就这么放弃么。于是，模式串从不匹配的那个字符开始从右向左寻找匹配串中不匹配的字符 b 的位置，结果发现居然有，赶快对上赶快对上，别耽误了。

匹配串：ab **cbcsd** xzcxx

模式串： **cbcac**

然后继续从最右边的字符从右向左进行比较。这时候，我们发现了，d-c 不匹配啊，而且模式穿里面没有噢，没办法，只好移动一个模式串长度的单位了。

匹配串：abcbcsd **xzcxx**

模式串： **cbcac**

Boyer-Moore 算法
****************************************

第二个上来的是 Boyer-Moore 算法。

是一个很复杂的算法，当然，虽然理论上时间复杂度和 KMP 差不多，但是实际上却比 KMP 快数倍，可见实践是检验真理的唯一标准。

原始论文：R.S.Boyer, J.S.Moore, A fast string searching algorithm , Communications of the ACM,20(10):762-772 ,1977

分为两步预处理，第一个是 bad-character heuristics ，也就是当出现错误匹配的时候，移位，基本上就是做的 Horspool 那一套。

第二个就是 good-suffix heuristics ，当出现错误匹配的时候，我还要从不匹配点向左看啊，以前匹配的那段子字符串是不是在模式串本身中还有重复的啊，有重复的话，那么我就直接把重复的那段和匹配串中已经匹配的那一段对齐就是了。再比较

匹配串： **abaccba** bbazz

模式串： **cbadcba**

我们看到已经匹配好了 cba ，但是 c-d 不匹配，这个时候我们发现既可以采用 bad-character heuristics ，也可以使用 good-suffix heuristics(模式串： **cba** d **cba** ) ，在这种情况下，邪不压正。毅然投奔 good 。移动得到

匹配串：abac **cbabbaz** z

模式串：**cbadcba**

可是，我们有时候也发现，已经匹配好的那一部分其实并没有再有重复了的啊。这个时候，我们发现已经匹配好的那串字符串有一部分在开头重新出现了，那么，赶快，对齐吧。

匹配串： **abacccb** bbazz

模式串： **cbadccb**

然后得到

匹配串：abacc **cbbbazz**

模式串： **cbadccb**

当两种 Good-Suffix 出现的时候，取移动距离最大的那个。

.. note::

   对于 BM 算法，好规则和坏规则，这里讲的不够明确，下面推荐一个讲解非常优秀的文章，可谓图文并茂啊，而且还是个 MM 写的。 `Boyer-Moore 经典单模式匹配算法 <http://blog.csdn.net/iJuliet/archive/2009/05/19/4200771.aspx>`_

Sunday 算法
****************************************

最后一个是 Sunday 算法，实际上比 Boyer-Moore 还快，呵呵。长江后浪推前浪。

原始论文：Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990

看原始论文的题目，D.M. Sunday 貌似是故意想气气 Boyer-Moore 两位大牛似的。呵呵。不过实际上的确 Sunday 算法的确比 BM 算法要快，而且更简单。

Sunday 的算法思想和 Horspool 有些相似，但是。当出现不匹配的时候，却不是去找匹配串中不匹配的字符在模式串的位置，而是直接找最右边对齐的右一位的那个字符在模式串的位置。

比如：

匹配串： **abcbc** zdxzc

模式串： **zbcac**

恩，这里我们看到 b-a 没有对上，我们就看匹配串中的 z 在模式串的位置，然后，嘿嘿。

匹配串：abcbc **zdxzc**

模式串：*zbcac**

如果模式串中的没有那个字符怎么办呢？很简单，跳过去呗。

匹配串： **abcbc** edxzcs

模式串： **zbcac**

e 不在模式串中出现

那么我们就

匹配串：abcbce **dxzcs**

模式串： **zbcac**

RK 算法
****************************************

(2009/10/20 补充)

某一天在图书馆的一本算法分析设计书上翻到的。思路很新颖！和大家分享下。

在串匹配的简单算法中，把文本每 m 个字符构成的字符段作为一个字段，和模式进行匹配检查。如果能对一个长度为 m 的字符串赋以一个 Hash 函数。那么显然只有那些与模式具有相同 hash 函数值的文本中的字符串才有可能与模式匹配，这是必要条件，而没有必要去考虑文本中所有长度为 m 的字段，因而大大提高了串匹配的速度。因此 RK 算法的思想和 KMP，BM，Sunday 等思路迥然不同！

.. note::

   事实上，之前的串匹配方法，是将模式串的一个一个字符作为小的特征去分别进行匹配，而 RK 算法则是将串整体作为一个特征！难就难在单个字符的特征很容易想得到，整体作为一个特征就没那么容易想得到了

如果把整体作为一个特征，那么如何快速的求出这个整体特征的特征值？？

模式串的特征值仅需求一次即可。对于文本中的任意 m 个字符构成的字串如何快速的求特征就是个难点了。

抛砖引玉，这里给出一个简单的特征计算。 将字符串的每一个字符看做一个数，那么这个字符串的就是一个数字数组，通

过积分向量可以快速任意一个长度子字符串的向量和。可以把字符串的对应的字符数组的元素和看做这个字符串整体特征。

这个特征是可以再 O（1）的时间内求出的。其实原始的 RK 算法里面是把字符串看做一个 26 进制数在计算特征的。这里就不啰

嗦了，有兴趣的可以深入查找

.. code-block:: none

   aabsee sds 模式串 ees
      ees

发现 see 向量和 == ees 的向量和

然后就对 see 和 ees 做逐个字符的比较。发现不匹配继续往下走

.. code-block:: none

   aabsees ds 模式串 ees
       ees

发现 ees 向量和 == ees 的向量和

然后就对 ees 和 ees 做逐个字符的比较。发现匹配 OK。

另外还有 字符串匹配自动机 后缀树算法（分在线和非在线两种）等 见如下文章。不能说那个比那个更好，各个算法都有自己的优势及最佳应用场合。参考：http://blog.csdn.net/yifan403/archive/2009/06/16/4272793.aspx

另外，关于多模式字符串匹配 有 AC 算法（字符串匹配自动机思想） WM 算法（BM 在多模式的推广应用）
参考：http://blog.csdn.net/ijuliet/category/498465.aspx  该女子的 blog 有很多好文章。

代码
****************************************

附上 sunday 代码：http://hi.baidu.com/kmj0217/blog/item/6f837f2f3da097311e3089cb.html

一种比 KMP 和 BM 更高效的匹配算法（如果想看原英文介绍，看下面分割线后的网址）

适用于：模式串较短的情况，最坏时间复杂性为 O(N*M)，不过一般没这么坏

Sunday 算法其实思想跟 BM 算法很相似，只不过 Sunday 算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有 在匹配串中出现则直接跳过，即移动步长 = 匹配串长度 + 1；否则，同 BM 算法一样其移动步长 = 匹配串中最右端的该字符到末尾的距离 + 1。

代码如下：

.. code-block:: cpp

   /*
   * 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;
   }


算法介绍以及实现伪码：http://www-igm.univ-mlv.fr/~lecroq/string/node19.html

.. code-block:: cpp

   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 */
      }
   }


// 第三个代码实现，貌似比较高效
http://hi.baidu.com/azuryy/blog/item/10d3d3460b97af0e6b63e5cd.html

头文件定义：

.. code-block:: cpp

   /* 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;
   };


源文件

.. code-block:: cpp

   /* 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;
   }

简单测试下：

.. code-block:: cpp

   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;
   }

strstr 的实现。

需要说明的是 strstr 是 c 语言提供的使用 Brute Force 实现的字符串匹配，简单、通用是其最大的优点。时间复杂度是 O(mn)

.. code-block:: cpp

   // 下面是 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);
   }

本文来自 CSDN 博客，转载请标明出处：http://blog.csdn.net/whoismickey/archive/2009/02/08/3869367.aspx

strstr:
   glibc 里的 strstr 函数用的是 brute-force(naive) 算法，它与其它算法的区别是 strstr 不对 pattern(needle) 进行预处理，所以用起来很方便。理论复杂度 O(mn), 实际上，平均复杂度为 O(n), 大部分情况下高度优化的算法性能要优于基于自动机的匹配算法，关于串匹配算法可参考 http://www-igm.univ-mlv.fr/~lecroq/string/ 。

   glibc 中使用了：

   #. Stephen R. van den Berg 的实现，在他的基础上，
   #. Tor Myklebust http://sources.redhat.com/ml/libc-alpha/2006-07/msg00028.html 给出了更复杂的实现，当然也更高效。

   BF 有一个重要性质是事先不用知道串的长度，而基于跳跃的算法是需要用字符串长度来判断结束位置的。如何快速的确定字符串结束位置，可参考 http://www.cppblog.com/ant/archive/2007/10/12/32886.html ，写的很仔细。

将两种思想结合起来，可以做出更快的 strstr（3）。约定

#. 为 strstrBerg;
#. 为 strstrBergo，
#. 为 lstrstr，
#. 为 glibc 中的 strstr，

简单测试了一下:
   从长度为 2k 的文本中查找长度为 1、2、9 的模式串，结果如下

   ===== ======== ======== ========
          1         2          9
   （1） 0.000006 0.000006 0.000012
   （2） 0.000007 0.000004 0.000008
   （3） 0.000002 0.000002 0.000005
   （4） 0.000005 0.000005 0.000011
   ===== ======== ======== ========

下载 strstr 和测试程序 ，
下载后执行::

   unzip testStrstr.zip
   cd testStrstr
   make test

基于 sse2 的 strstr 函数 是用 sse2 指令集对 strstr 的优化