5.6　朴素的模式匹配算法

记得我在刚做软件开发的时候，需要阅读一些英文的文章或帮助。此时才发现学习英语不只是为了过四六级，工作中它还是挺重要的。而我那只为应付考试的英语，早已经忘得差不多了。于是我想在短时间内突击一下，很明显，找一本词典从头开始背不是什么好的办法。要背也得背那些最常用的，至少是计算机文献中常用的，于是我就想自己写一个程序，只要输入一些英文的文档，就可以计算出这当中所用频率最高的词汇是哪些。把它们都背好了，基本上阅读也就不成问题了。

当然，说说容易，要实现这一需求，当中会有很多困难，有兴趣的同学，不妨去试试看。不过，这里面最重要其实就是去找一个单词在一篇文章（相当于一个大字符串）中的定位问题。这种子串的定位操作通常称做串的模式匹配，应该算是串中最重要的操作之一。

假设我们要从下面的主串S="goodgoogle"中，找到T="google"这个子串的位置。我们通常需要下面的步骤。

1．主串S第一位开始，S与T前三个字母都匹配成功，但S第四个字母是d而T的是g。第一位匹配失败。如图5-6-1所示，其中竖直连线表示相等，闪电状弯折连线表示不等。

5.6　朴素的模式匹配算法 - 图1

图5-6-1

2．主串S第二位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败，如图5-6-2所示。

5.6　朴素的模式匹配算法 - 图2

图5-6-2

3．主串S第三位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败，如图5-6-3所示。

5.6　朴素的模式匹配算法 - 图3

图5-6-3

4．主串S第四位开始，主串S首字母是d，要匹配的T首字母是g，匹配失败，如图5-6-4所示。

5.6　朴素的模式匹配算法 - 图4

图5-6-4

5．主串S第五位开始，S与T，6个字母全匹配，匹配成功，如图5-6-5所示。

5.6　朴素的模式匹配算法 - 图5

图5-6-5

简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。

前面我们已经用串的其他操作实现了模式匹配的算法Index。现在考虑不用串的其他操作，而是只用基本的数组来实现同样的算法。注意我们假设主串S和要匹配的子串T的长度存在S[0]与T[0]中。实现代码如下：

  1. /* 返回子串T在主串S中第pos个字符之后的位置。
  2. 若不存在，则函数返回值为0。 */
  3. /* T非空，1≤pos≤StrLength(S)。 */
  4. int Index(String S, String T, int pos)
  5. {
  6.     /* i用于主串S中当前位置下标，若pos不为1 */
  7.     /* 则从pos位置开始匹配 */
  8.     int i = pos;                      
  9.     /* j用于子串T中当前位置下标值 */
  10.     int j = 1;                        
  11.     /* 若i小于S长度且j小于T的长度时循环 */
  12.     while (i <= S[0] && j <= T[0])    
  13.     {
  14.         /* 两字母相等则继续 */
  15.         if (S[i] == T[j])             
  16.         {
  17.             ++i;
  18.             ++j;
  19.         }
  20.         /* 指针后退重新开始匹配 */
  21.         else                          
  22.         {
  23.             /* i退回到上次匹配首位的下一位 */
  24.             i = i - j + 2;            
  25.             /* j退回到子串T的首位 */
  26.             j = 1;                    
  27.         }
  28.     }
  29.     if (j = T[0])
  30.         return i - T[0];
  31.     else
  32.         return 0;
  33. }

分析一下，最好的情况是什么？那就是一开始就区配成功，比如“googlegood”中去找“google”，时间复杂度为O(1)。稍差一些，如果像刚才例子中第二、三、四位一样，每次都是首字母就不匹配，那么对T串的循环就不必进行了，比如“abcdef-google”中去找“google”。那么时间复杂度为O(n+m)，其中n为主串长度，m为要匹配的子串长度。根据等概率原则，平均是(n+m)/2次查找，时间复杂度为O(n+m)。

那么最坏的情况又是什么？就是每次不成功的匹配都发生在串T的最后一个字符。举一个很极端的例子。主串为S="00000000000000000000000000000000000000000000000001"，而要匹配的子串为T="0000000001"，前者是有49个“0”和1个“1”的主串，后者是9个“0”和1个“1”的子串。在匹配时，每次都得将T中字符循环到最后一位才发现：哦，原来它们是不匹配的。这样等于T串需要在S串的前40个位置都需要判断10次，并得出不匹配的结论，如图5-6-6所示。

5.6　朴素的模式匹配算法 - 图6

图5-6-6

直到最后第41个位置，因为全部匹配相等，所以不需要再继续进行下去，如图5-6-7所示。如果最终没有可匹配的子串，比如是T="0000000002"，到了第41位置判断不匹配后同样不需要继续比对下去。因此最坏情况的时间复杂度为O((n-m＋1)*m)。

5.6　朴素的模式匹配算法 - 图7

图5-6-7

不要以为我这只是危言耸听，在实际运用中，对于计算机来说，处理的都是二进位的0和1的串，一个字符的ASCII码也可以看成是8位的二进位01串，当然，汉字等所有的字符也都可以看成是多个0和1组成的串。再比如像计算机图形也可以理解为是由许许多多个0和1的串组成。所以在计算机的运算当中，模式匹配操作可说是随处可见，而刚才的这个算法，就显得太低效了。