学步园

【注】本文参考了数据结构和算法方面的书籍和网上资料。

字符串模式匹配有着广泛的应用，如求最大公共子串、最长回文字符串、L-Gap、数据压缩、DNA序列匹配等问题。所谓模式匹配就是在目标字符串中寻找字串的过程，要寻找的字串即为模式。

目前主流的模式匹配算法不外乎BF、KMP、BM等等。本小节主要讨论前两个算法。

BF(Bruce Force)算法可以说是模式匹配算法中最简单、最容易理解的一个。原理很简单。其基本思想是从主串的start位置开始与模式串进行匹配，如果相等，则继续比较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1位置，继续进行比较直至模式串的所有字符都已比较成功则匹配成功，或者主串所有的字符已经比较完毕，没有找到完全匹配的字串，则匹配失败。

该算法较为简单，代码如下：

//start 为从第start位置的字符开始比较，默认为0

int BF(char s[], char d[], int start = 0)

{

      char *p = s + start; //记录开始比较的位置

      int index = start - 1; //记录位置，以便成功时返回字串在主串的位置

      char *q = d;

      char *tmp;

      while (*p != '/0')

      {

             tmp = p;

             ++index;

             while (*q != '/0' && *tmp != '/0' && *tmp == *q)

             {

                    ++tmp;

                    ++q;

             }

             if (*q == '/0') //匹配成功，返回结果

                    return index;

             else //主串和模式串回溯

             {

                    ++p;

                    q = d;

             }

      }

      return -1; //匹配失败

}

下面开始讨论比较麻烦的KMP算法。

KMP算法是有Knuth、Morris、Pratt提出的。目的是为了解决BF算法中不必要的回溯。下面着重讨论一下其原理。

假设主串为T，模式为P。BF算法的匹配过程如下：

首先P中的第一个字符与T中的第一个字符比较,

T_oT₁T₂……T_n

P₀P₁P₂……Pm，假设在T₂和P₂匹配时失败，则可以知道T₀T₁一定与P₀P₁相同。那么T可以等价的改为P₀P₁T₂T₃……T_n。则下次比较为:

P₀P₁T₂……T_n

P₀P₁P₂……Pm。可以看到这次比较时从P₁和P₀比较开始的。同样假设是在T_k和P_k-1比较时失败，则T₁T₂T₃……T_kT_k+1……T_n可以等价的替换为P₀P₀P₁P₂……P_k-2T_k……T_n，下次匹配为：

P₀P₀P₁P₂……P_k-2T_k……T_n

    P₀P₁P₂……P_k……P_m。可以看到前面一大段字符基本上是P在和自己匹配，而如果可以事先获得P中字符之间的某种关系，则这些中很多不必要的匹配都可以省去了，可以极大的提高匹配的效率。例如T=babaaac，P=aac，在第二轮匹配时，T₃=b与P₂=a匹配失败，按照BF算法下次有应该是T₃和P₁开始匹配，但是我们看以看出P₁和P₂是相等的，既然P₂和T₃不相等，那么也就没有比较继续T₃和P₁的比较了，这样就避免了很多不必要的比较。而这种字符之间的关系就是大家非常熟悉的next数组。

有了next数组之后，如果P_j与T_i匹配失败后不是像BF算法那样P回溯到开始，T指针后移一位继续比较，而是利用P字符之间的关系，T指针不回溯，模式串P像右滑动一段距离，P_next[j]继续和T_i匹配，这样就省去了很多不必要的匹配和回溯，提高了效率。而next数组中的值也就是T_j匹配失败是下一次与主串进行匹配的模式串的字符下标。此时模式匹配算法KMP的代码如下：

//s为主串，d为模式串，next为next数组，lens为s的长度，

//lend为d的长度

//start为s中开始比较的字符下标

int kmp(char *s, char *d, int *next, int lens, int lend, int start = 0)

{

      char *p = s + start; //p指向T中开始匹配的位置

      char *q = d;   //q指向P的起始位置

      int i = 0, j = 0;

      while (i < lens && j < lend)   //放置越界访问

      {

             //     j=-1表示P已经回溯到起始位置但是还是不能与主串中的Ti

             // 匹配成功，则T指针后移一位,继续匹配

             if (j == -1 || *(p + i) == *(q + j))

             {

                    ++i;

                    ++j;

             }

             else //匹配失败且P指针没有回溯到起始位置，

             {     //则用next[j]继续与Ti进行匹配

                    j = next[j] ;

             }

      }

      if (*(q + j) == '/0') //q指向P的结束位置,表示匹配成功

             return i - j;

      else                  //匹配失败

             return -1;

}

这里与很多书上介绍的KMP算法不太一致，C语言中字符串的第一个位置并不是保存的字符串的长度，故这里对算法稍加改造，next数组与书中的next数组的求法整体相比小1，即next[0]等于-1而不是0，后面的值也较之小1。这样可以很方便的在C和类C的语言中使用。

这个算法本身并不难理解，难理解的就是next数组的意义和其求法，下面着重讨论这个问题。

同样假设主串为T，模式串为P，在T_i和P_j进行匹配时匹配失败。则可以得知：P₀P₁P₂……P_j-1=T_i-jT_i-j+1……T_i-11，

同时假设下次应该由P_k与T_i开始进行下一轮的匹配。则可以得出：

P₀P₁P₂……