串或字符串属于线性结构，自然地可以直接利用向量或列表等序列结构加以实现。但字符串作为一种数据结构，特点极其鲜明，作为字符串基本组成元素的字符，种类通常不多，甚至可能极少。因此，为了高效地处理以字符串形式表示的海量数据，需要设计专门的处理方法。

本章直接利用C++所提供的字符数组，将重点几种在串匹配算法的设计、实现与优化。在此类应用中，更多地是以某一局部子串为单位，考查其对应的模式（pattern），因此也称作循模式访问（call-by-pattern）。

1.串及串匹配

1.1.串

字符串：

由来自字母表$\sum$的字符所组成的有限序列，$S=”a_0\,a_1\,a_2\dots\,a_{n-1}”$，其中$a_i\in \sum, 0 \le i < n$。这里的$\sum$是所有可用字符的集合，称作字符表（alphabet）。字符串S所含的字符的总数n，称作S的长度，记作$|S|=n$，长度为0的串称作空串（null string）。通常，字符的种类不多，而串长$=n>>|\sum|$。

子串：

字符串中任一连续的片段，称作其子串（substring）。对于任意的$0\le i \le i+k <n$，由字符串S中起始于位置i的连续k个字符组成的子串记作：S.substr(i, k) = S[i, i+k)。

起始于位置0，长度为k的子串称为前缀（prefix）：S.prefix(k) = S.substr(0,k) = S[0,k)。

终止于位置n-1、长度为k的子串称为后缀（suffix）：S.suffix(k) = S.substr(n-k,k) = S[n-k,n)。

空串是任何字符串的子串，也是任何字符串的前缀和后缀；任何字符串都是自己的子串，也是自己的前缀和后缀。此类子串。前缀和后缀分别称作平凡子串（trivial substring）、平凡前缀（trivial prefix）和平凡后缀（trivial suffix）。反之，字符串本身之外的所以非空子串。前缀和后缀，分别称作真子串（proper substring）、真前缀（proper prefix）和真后缀（proper suffix）。

判等：

字符串S[0,n)和T[0,m)称作相等，当且仅当二者长度相等（n=m），且对应字符分别相同。

ADT：

串结构主要的操作接口可归纳为下表：

操作接口	功能
`length()`	查询串的长度
`charAt(i)`	返回第`i`个字符
`substr(i,k)`	返回从第`i`个字符起，长度为`k`的子串
`prefix(k)`	返回长度为`k`的前缀
`suffix(k)`	返回长度为`k`的后缀
`equal(T)`	判断T是否与当前字符串相等
`concat(T)`	将T串接在当前字符串之后
`indexOf(P)`	若P是当前字符串的一个子串，则返回该子串的起始位置；否则返回-1

下面是一些实例：

1.2.串匹配

在涉及字符串的众多实际应用中，模式匹配是最常使用的一项基本操作。如在生物信息处理领域需要在蛋白质序列中寻找特定的氨基酸模式，或在DNA序列中寻找特定的碱基模式。再如邮件过滤器也需要根据事先定义的特征串，通过扫描电子邮件的地址、标题及正文来识别垃圾邮件等等。

上述所有应用问题，本质上都可转化和描述为如下形式：如何在字符串数据中，检测和提取以字符串形式给出的某一局部特征。这类操作都属于串模式匹配（string pattern matching）范畴，简称串匹配。一般地，即：

对基于同一字符表的任何文本串T（|T| = n）和模式串P（|P| = m），判定T中是否存在某一子串与P相同，若存在（匹配），则报告该子串在T中的起始位置。

串的长度n和m本身通常都很多，但相对而言n更大，即满足$2 \ll m \ll n$。

根据具体应用的要求不同，串匹配问题有多种形式：

模式检测（pattern detection）问题：只关心是否存在匹配而不关心具体的匹配位置，如垃圾邮件的检测；
模式定位（pattern location）问题：若经判断的确存在匹配，则还需确定具体的匹配位置；
模式计数（pattern counting）问题：若有多处匹配，则统计出匹配子串的总数；
模式枚举（pattern enumeration）问题：在有多处匹配时，报告出所有匹配的具体位置。

鉴于串结构自身的特点，在设计和分析串模式匹配算法时也必须做特殊的考虑，一个重要的问题是：如何对任一串匹配算法的性能作出客观的测量和评估。不幸的是评估算法性能的常规口径和策略并不适用于这一问题，因为若假设文本串T和模式串P都是随机生成的，那么计算得到的匹配成功的概率往往极低。

实际上，有效涵盖成功匹配情况的一种简便策略是，随机选取文本串T，并从T中随机取出长度为m的子串作为模式串P，这即是文本将采用的评价标准。

2.蛮力算法

蛮力串匹配是最直接的方法，不妨按自左向右的次序考查子串，逐个字符对比。如下图，模式串P的每一黑色方格对应于字符的一次匹配，每一灰色方格对应于一次失败，白色方格对应于未进行的一次对比。若经过检查，当前的m对字符均匹配，则意味着整体匹配成功，从而返回匹配子串的位置。

蛮力算法的正确性显而易见，既然只有在某一轮的m次比对全部成功之后才成功返回，故不致于误报；反过来，所有对齐位置都会逐一尝试，故亦不致漏报。

下面是蛮力算法的两个实现版本，二者原理相同、过程相仿，但分别便于引入后续的不同改进算法，故在此先做一比较。

版本一：

/************************************************************************************
 * Text     :  0   1   2   .   .   .   i-j .   .   .   .   i   .   .   n-1
 *             ------------------------|-------------------|------------
 * Pattern  :                          0   .   .   .   .   j   .   .
 *                                     |-------------------|
 ***********************************************************************************/
int match ( char* P, char* T ) { //串匹配算法（Brute-force-1）
   size_t n = strlen ( T ), i = 0; //文本串长度、当前接受比对字符的位置
   size_t m = strlen ( P ), j = 0; //模式串长度、当前接受比对字符的位置
   while ( j < m && i < n ) //自左向右逐个比对字符
      /*DSA*/{
      /*DSA*/showProgress ( T, P, i - j, j );   getchar();
      if ( T[i] == P[j] ) //若匹配
         { i ++;  j ++; } //则转到下一对字符
      else //否则
         { i -= j - 1; j = 0; } //文本串回退、模式串复位
      /*DSA*/}
   return i - j; //如何通过返回值，判断匹配结果？i-j<=n-m就表示成功，反之失败
}

版本二：

/************************************************************************************
 * Text     :  0   1   2   .   .   .   i   i+1 .   .   .   i+j .   .   n-1
 *             ------------------------|-------------------|------------
 * Pattern  :                          0   1   .   .   .   j   .   .
 *                                     |-------------------|
 ***********************************************************************************/
int match ( char* P, char* T ) { //串匹配算法（Brute-force-2）
   size_t n = strlen ( T ), i = 0; //文本串长度、与模式串首字符的对齐位置
   size_t m = strlen ( P ), j; //模式串长度、当前接受比对字符的位置
   for ( i = 0; i < n - m + 1; i++ ) { //文本串从第i个字符起，与
      for ( j = 0; j < m; j++ ) //模式串中对应的字符逐个比对
         /*DSA*/{showProgress ( T, P, i, j ); getchar();
         if ( T[i + j] != P[j] ) break; //若失配，模式串整体右移一个字符，再做一轮比对
         /*DSA*/}
      if ( j >= m ) break; //找到匹配子串
   }
   return i; //如何通过返回值，判断匹配结果？i<=n-m就表示成功，反之失败
}

时间复杂度：

从理论上讲，蛮力算法至多迭代n-m+1轮，且各轮至多需要进行m次比对，故总共只需做不超过$(n-m+1)\cdot m$次比对，其中成功的和失败的各有$(m-1)\cdot (n-m+1)+1$和$n-m-2$次。因$m\ll n$，渐进的时间复杂度应为$O(n\cdot m)$。

蛮力算法的效率也并非总是如此低下，如上右图，若将模式串P左右颠倒，则每经一次比对都可排除文本串中的一个字符，故此类情况下的运行时间将为$O(n)$。实际上，此类最好（或接近最好）情况出现的概率并不很低，尤其是在字符表较大时。

3.KMP算法

3.1.构思

蛮力算法在最坏情况下所需时间，为文本串长度与模式长度的乘积，故无法应用于规模稍大的应用环境，很有必要改进。为此，不妨从最坏情况入手，最坏情况在于这里存在大量的局部匹配：每一轮的m次比对中，仅最后一次可能失配，而一旦发现失配，文本串、模式串的字符指针都要回退，并从头开始下一轮尝试。实际上，这列重复的字符比对操作没有必要。既然这些字符在前一轮迭代中已经接受过比对并且成功，我们也就掌握了它们的所有信息。接下来就要考虑如何利用这些信息，提高匹配算法的效率。

如下图，用T[i]和P[j]分别表示当前正在接受比对的一对字符。当本轮比对进行到最后一对字符并发现失配后，蛮力算法令两个字符指针同步回退（即令i = i - j + 1和j = 0），然后再从这一位置继续比对，然而事实上，指针i完全不必回退。

因为经过前一次的比对，我们已经知道子串T[i-j,i)完全由'0'组成，便可预测出：在回退之后紧接着的下一轮对比中，前j-1次比对必然都会成功。因此可直接令i保持不变，令j=j-1，然后继续比对。如此下一轮只需1次比对，共减少j-1次。这个操作可以理解为：令P相对于T右移一个单元，然后从前一失配位置继续比对。实际上这一技巧可以推广：利用以往的成功比对所提供的信息（记忆），不仅可避免文本串字符指针的回退，而且可使模式串尽可能大跨度地右移（经验）。下面是一个更一般的例子：

3.2.next表

一般地，假设前一轮比对终止于T[i] $\ne$ P[j]，按以上构思，指针i不必回退，而是将T[i]与P[t]对齐并开始下一轮对比。接下来考虑t的值应该取作多少。

如上图，经过此前一轮的对比，已经确定匹配的范围应为：P[o,j) = T[i-j,i)。

于是，若模式串P经适当右移之后，能够与T的某一（包含T[i]在内的）子串完全匹配，则一项必要条件就是：P[0,t) = T[i-t,i) = P[j-t,j)，亦即，在P[0,j)中长度为t的真前缀，应与长度为t的真后缀完全匹配，故t必来自集合：

$N(P,j)=\{0\le t \le j \,\,\,|\,\,\,P[0,t)=P[j-t,j)\}$

一般地，该集合可能包含多个这样的t，而需要注意的是，t的值仅取决于模式串P以及前一轮比对的首个失配位置P[j]，而与文本串T无关。若下一轮比对将从T[i]与P[t]的比对开始，这等效于将P右移j-t个单元，位移量与t成反比。因此为保证P与T的对齐位置（指针i）绝不倒退，同时又不致遗漏任何可能的匹配，应在集合N(P,j)中挑选最大的t，即当有多个右移方案时，应该保守地选择其中移动距离最短者。

于是令：next[j] = max( N(P,j) )，则一旦发现P[i]与T[i]失配，即可转而将P[ next[i] ]与T[i]彼此对准，并从这一位置开始继续下一轮比对。

既然集合N(P,j)仅取决于模式串P以及失配位置j，而与文本串无关，作为其中的最大元素，next[j]也必然具有这一性质。对于任一模式串P，不妨通过预处理提前计算出所有位置j所对应的next[j]值，并整理为表格以表此后反复查询。

3.3.KMP算法

上述思路可整理为如下代码，即著名的KMP算法。对照此前的蛮力算法，只是在else分支对失配情况的处理手法有所不同，这也是KMP算法的精髓所在。

int match ( char* P, char* T ) {  //KMP算法
   int* next = buildNext ( P ); //构造next表
   int n = ( int ) strlen ( T ), i = 0; //文本串指针
   int m = ( int ) strlen ( P ), j = 0; //模式串指针
   while ( j < m  && i < n ) //自左向右逐个比对字符
      //*DSA*/ {
      //*DSA*/ showProgress ( T, P, i - j, j );
      //*DSA*/ printNext ( next, i - j, strlen ( P ) );
      //*DSA*/ getchar(); printf ( "\n" ); */
      if ( 0 > j || T[i] == P[j] ) //若匹配，或P已移出最左侧（两个判断的次序不可交换）
         { i ++;  j ++; } //则转到下一字符
      else //否则
         j = next[j]; //模式串右移（注意：文本串不用回退）
      //*DSA*/ }
   delete [] next; //释放next表
   return i - j;
}

next[0] = -1

只要j>0，则必有$0\in N(P,j)$。此时N(P,j)非空，从而可以保证“ 在其中取最大值 ”这一操作的确可行。但反过来，若j=0，则即便集合N(P,j)可以定义，也必是空集。反观串匹配的过程，若在某一轮比对中首对字符即失配，则应将P直接右移一个字符，然后启动下一轮比对。如下表，不妨假想地在P[0]的左侧“ 附加 ”一个P[-1]，且该字符与任何字符都是匹配的，就实际效果而言，这一处理方法完全等同于“ 令next[0] = -1 ”。

next[j+1]

若已知next[0,j]，如何才能递推地计算出next[j+1]？若next[j]=t，则意味着在P[0,j]中，自匹配的真前缀和真后缀的最大长度为t，故必有next[j=1] $\le$ next[j]+1，当且仅当P[j]=P[t]时，取等号。如下图：

一般地，若P[j] $\ne$ P[t]，由next表的功能定义，next[j+1]的下一候选者应该依次是：

next[ next[j] ] + 1，next[ next[ next[j] ] ] + 1，……

因此只需反复用next[t]替换t（即令t = next[t]），即可按优先次序遍历以上候选者；一旦发现P[j]与P[t]匹配（含与P[t=-1]的通配），即可令next[j+1] = next[t] + 1。

既然总有next[t] < t，故在此过程中t必然严格递减；同时，即便t降低至0，亦必然会终止于通配的next[0] = -1，而不致下溢，如此该算法的正确性完全可以保证。

构造next表：

按照以上思路，可实现next表构造算法如下。next表的构造算法与KMP算法几乎完全一致，实际上按照以上分析，这一构造过程完全等效于串的自我匹配，因此两个算法在形式上的近似亦不足为怪。

int* buildNext ( char* P ) { //构造模式串P的next表
   size_t m = strlen ( P ), j = 0; //“主”串指针
   int* N = new int[m]; //next表
   int t = N[0] = -1; //模式串指针
   while ( j < m - 1 )
      if ( 0 > t || P[j] == P[t] ) { //匹配
         j ++; t ++;
         N[j] = t; //此句可改进...
      } else //失配
         t = N[t];
   //*DSA*/printString ( P ); printf ( "\n" );
   //*DSA*/printNext ( N, 0, m );
   return N;
}

性能分析：

由上可见，KMP算法借助next表可避免大量不必要的字符比对操作，但这意味着渐渐意义上的时间复杂度会有实质改进嘛？

为此的证明需要一些技巧，若令k = 2i - j，并考查k在KMP算法过程中的变化趋势，则不难发现，while循环每迭代一轮，k都会严格递增。对于while循环内部的if - else分支，无非两种情况：若转入if分支，则i和j同时加一，于是k = 2i -j必将增加；反之若转入else分支，则尽管i保持不变，但在赋值j = next[j] 之后j必然减少，于是k = 2i -j也必然增加。

纵观算法的整个过程：启动时有i =j =0，即k =0；算法结束时$i\le n$或$j \ge 0$，故有$k\le 2n$。在此期间尽管整数k从0开始持续地严格递增，但累计增幅不超过$2n$，故while循环至多执行$2n$轮。另外，while循环体内部不含任何循环或调用，故只需$O(1)$时间，因此若不计构造next表所需的时间，KMP算法本身的运行时间不超过$O(n)$。也就是说，尽管可能有$\Omega(n)$个对齐位置，但就分摊意义而言，在每一对齐位置仅需$O(1)$次对比。

既然next表构造算法的流程与KMP算法并无实质区别，故仿照上述分析可知，next表的构造仅需$O(m)$时间，综上，KMP算法的总体运行时间为$O(n+m)$。

3.4.改进

尽管以上KMP算法已可保证线性的运行时间，但在某些情况下仍有进一步改进的余地。如下面的例子，按照此前定义的next表，仍会进行多次本不必要的字符比对操作。前一轮对比因T[i] = '1' $\ne$ '0' = P[3]失配而中断，接下来KMP算法将依次将P[2]、P[1]和P[0]与T[i]对准并做比对。

不难发现原因出在 P[3] = P[2] =P[1] = '0'，而此前比对已发现T[i] $\ne$ P[3]，那么继续将T[i]和那些与P[3]相同的字符做比对，就是徒劳无功的。

就算法策略而言，引入next表的实质作用在于帮助我们利用以往成功比对所提供的“ 经验 ”，而实际上，此前已进行过的比对还远远不止这些，确切地说还包括那些失败的比对——作为“ 教训 ”。为把这类“ 负面 ”信息引入next表，只需将集合$N(P,j)$的定义修改为：

$N(P,j)=\{0\le t < j\,\,\,|\,\,\,P[0,t)=P[j-t,j)且P[t] \ne P[j]\}$

也就是说，除“ 对应于自匹配长度 ”以外，t只要还同时满足“ 当前字符对不匹配 ” 的必要条件，方能归入集合$N(P,j)$并作为next表项的候选。

相应地，原next表构造算法也需稍作修改如下：

int* buildNext ( char* P ) { //构造模式串P的next表（改进版本）
   size_t m = strlen ( P ), j = 0; //“主”串指针
   int* N = new int[m]; //next表
   int t = N[0] = -1; //模式串指针
   while ( j < m - 1 )
      if ( 0 > t || P[j] == P[t] ) { //匹配
         N[j] = ( P[++j] != P[++t] ? t : N[t] ); //注意此句与未改进之前的区别
      } else //失配
         t = N[t];
   /*DSA*/printString ( P ); printf ( "\n" );
   /*DSA*/printNext ( N, 0, strlen ( P ) );
   return N;
}

改进后的算法与原算法的唯一区别在于，每次在P[0,j)中发现长度为t的真前缀和真后缀相互匹配之后，还需进一步检查P[j]是否等于P[t]。唯有在P[j] $\ne $ P[t]时，才能将t赋予next[j]；否则需转而代之以next[t]，改进后next表的构造算法同样只需$O(m)$时间。

将改进后的KMP算法应用于前面的例子，在首轮比对因T[i] = '1' $\ne$ '0' = P[3]失配而中断之后，将随机以P[ next[3] ] = P[-1]与T[i]对齐，并进行下一轮比对。这样就等同于聪明且安全地跳过了三个不必要的对齐位置。

4.BM算法

4.1.构思

KMP算法的思路可概括为：当前比对一旦失配，即利用此前的比对所提供的信息，尽可能长距离地移动模式串。其精妙之处在于，无需显式地反复保存或更新比对的历史，而是独立于具体的文本串，事先根据模式串预测出所有可能出现的失配情况，并将这些信息记录于next表中。

回顾之前的知识不难发现：串匹配 = x次失败的对齐 + 0/1次成功的对齐，这样与其说要加速匹配，不如说是要加速失败——尽快排除失败的对齐。就单个对齐的位置的排除而言：平均仅需常数次比对（只要$|\sum|$不致太小，单次比对成功概率足够低），且具体的比对位置及次序无所谓。然后就排除更多后续对齐位置而言，不同的对比位置及次序，作用差异极大。通常是越靠前的位置，作用越小；越靠后的位置，作用越大。

BM算法与KMP算法类似，二者的区别仅在于预测和利用“ 历史 ”信息的具体策略与方法。BM算法中，模式串P与文本串T的对准位置依然“ 自左向右 ”推移，而在每一对准位置确实“ 自右向左 ”地逐一比对各字符。具体地，在每一轮自右向左的比对过程中，一旦发现失配，则将P右移一定距离并再次与T对准，然后重新一轮自右向左的扫描比对。

BM算法的主题框架，可实现为如下代码：

//////////////////////////////////////////////////////////////////////////
// Boyer-Moore算法
//////////////////////////////////////////////////////////////////////////
void     ShowProgress ( String, String,  int,  int );
#define  CARD_CHAR_SET     256   //Cardinality of charactor set
int*     BuildBC ( String ); //构造Bad Charactor Shift表
int*     suffixes ( String );
int*     BuildGS ( String ); //构造Good Suffix Shift表

int match ( char* P, char* T ) { //Boyer-Morre算法（完全版，兼顾Bad Character与Good Suffix）
   int* bc = buildBC ( P ); int* gs = buildGS ( P ); //构造BC表和GS表
   size_t i = 0; //模式串相对于文本串的起始位置（初始时与文本串左对齐）
   while ( strlen ( T ) >= i + strlen ( P ) ) { //不断右移（距离可能不止一个字符）模式串
      int j = strlen ( P ) - 1; //从模式串最末尾的字符开始
      while ( P[j] == T[i + j] ) //自右向左比对
         if ( 0 > --j ) break; /*DSA*/showProgress ( T, P, i, j ); printf ( "\n" ); getchar();
      if ( 0 > j ) //若极大匹配后缀 == 整个模式串（说明已经完全匹配）
         break; //返回匹配位置
      else //否则，适当地移动模式串
         i += __max ( gs[j], j - bc[ T[i + j] ] ); //位移量根据BC表和GS表选择大者
   }
   delete [] gs; delete [] bc; //销毁GS表和BC表
   return i;
}

这里采用了蛮力算法后一版本的方式，借助整数i和j指示文本串中当前的对齐位置T[i]和模式串中接受比对的字符P[j]。一旦局部失配，采用两种启发式策略确定最大的安全移动距离，为此需要经过预处理，根据模式串P整理出坏字符和好后缀两类信息。与KMP算法一样，算法过程中指针i始终单调递增；相应地，P相对于T的位置也绝不回退。

4.2.坏字符策略

如下图中(a)和(b)，若模式串P当前在文本串T中的对齐位置为i，且在这一轮自右向左将P与substr(T,i,m)的比对过程中，在P[j]处首次发现失配：T[i+j] = 'X' $\ne$ 'Y' = P[j]，则将'X'称作坏字符（bad character）。接下来考虑应该选择P中哪个字符对准T[i+j]。

若P与T的某一（包括T[i+j]在内的）子串匹配，则必然在T[i+j] = 'X'处匹配；反之，若与T[i+j]对准的字符不是'X'，则必然失配。故如图(c)，只需找出P中的每一字符'X'，分别于T[i+j] = 'X'对准，并执行一轮自右向左的扫描比对。

若P中包含多个'X'，其实并没有必要逐一尝试，逐一对比并无法确保文本串指针i永不回退。一种简便而高效的做法是：仅尝试P中最靠右的字符'X'（若存在）。如此便可在确保不致遗漏匹配的前提下，始终单向地滑动模式串，如上图(c)若P中最靠右的字符'X'为P[k] = 'X'，则P的右移量即为j-k。

bc[ ]表：

对于任一给定的模式串P，k值只取决于字符T[i+j] = 'X'，因此可将其视作从字符表到整数（P中字符的秩）的一个函数：

$bc(c)=\begin{cases} k,\quad &若P[k]=c，且对所有的i>k都有P[i] \ne c\\ -1,\quad &若P[\,\,\,]中不含字符c \end{cases}$

故如当前对齐位置为i，则一旦出现坏字符P[j] = 'Y'，即重新对齐与：i += j - bc[ T[i+j] ]，并启动下一轮比对。为此可预先将函数bc()整理为一份查询表，称作BC表。

接下来考虑BC表中可能出现的两种特殊情况：若P根本就不含坏字符'X'，如上图(d)，则模式串整体移过失配位置T[i+j]，用P[0]对准T[i+j+1]，再启动下一轮比对，此类字符在BC表的对应项置为-1，其效果也等同于在模式串的最左端，增添一个通配符。若P中含有坏字符'X'，但其中最靠右者的位置也可能太靠右，以至于j-k < 0，相当于左移模式串。显然这是不必要的——匹配算法能进行到此，则此前左侧的所有位置已被显式或隐式地否定排除了，因此只需将P串右移一个单位，然后启动下一轮自右向左的比对。

以由大写字母和空格组成的字符表为例，与模式串”DATA STRUCTURES”相对应的BC表如下所示：

按照以上思路，BC表的构造算法可实现如下：

//***********************************************************************************
//    0                       bc['X']                                m-1
//    |                       |                                      |
//    ........................X***************************************
//                            .|<------------- 'X' free ------------>|
//***********************************************************************************
int* buildBC ( char* P ) { //构造Bad Charactor Shift表：O(m + 256)
   int* bc = new int[256]; //BC表，与字符表等长
   for ( size_t j = 0; j < 256; j ++ ) bc[j] = -1; //初始化：首先假设所有字符均未在P中出现
   for ( size_t m = strlen ( P ), j = 0; j < m; j ++ ) //自左向右扫描模式串P
      bc[ P[j] ] = j; //将字符P[j]的BC项更新为j（单调递增）——画家算法
   /*DSA*/printBC ( bc );
   return bc;
}

如上的算法在对BC初始化之后，对模式串P做一遍线性扫描，并不断用当前字符的秩更新BC表中的对应项。因为是按秩递增的次序从左到右扫描，故只要字符c在P中出现过，则最终的bc[c]必会记录下其中最靠右者的秩，这类算法也因此被称作“ 画家算法 ”（painter’s algorithm）。

算法的运行时间可以分为两部分，分别消耗于其中的两个循环：前者是对字符表$\sum$中的每个字符分别做初始化，时间量不超过$O(|\sum|)$；后一循环对模式串P做一轮扫描，其中每个字符消耗$O(1)$时间，需要$O(m)$时间。因此BC表构造消耗时间为$O(|\sum|+m)$。

下面是一个运用BM_BC算法的实例：

整个过程总共做过6次成功的比对（黑色字符）和4次失败的比对（白色字符），累计10次，文本串的每个有效字符平均为10/11不足一次。

复杂度：

BM算法本身进行串模式匹配所需的时间与具体的输入十分相关，将文本串和模式串的长度分别记为n和m，则在通常情况下的实际运行时间往往低于$O(n)$。在最好情况下，每经过常数次比对，就可以将模式串右移m个字符（即整体右移），如下图中的一类情况（对应蛮力算法中的最坏情况），只需$n/m$次比对算法即可终止，故最好情况下BM算法只需$O(n/m)$时间。

如将模式串P左右颠倒，则对应着最坏的一类情况，在每一轮比对中，P总要完整地扫描一遍才发现失配并向右移动一个字符，运行时间需要$O(n \times m)$。

4.3.好后缀策略

参照KMP算法的改进思路不难发现，坏字符策略仅利用了此前（最后一次）失败比对所提供的“ 教训 ”。而实际上在此之前，还做过一系列成功的比对，但这些“ 经验 ”却被忽略了。如上图，每当在P[0] ='1' $\ne$ '0' 处失配，自然地想到应该将其替换成字符'0'。但既然本轮比对过程中已有大量字符'0'的成功匹配，则无论将P[0]对准其中的任何一个都注定会失配。故此时更应明智地将P整体移过这段区间，直接以P[0]对准T中尚未接受比对的首个字符，如此算法的运行时间将有望降回至$O(n)$。

好后缀：

每轮比对中的若干次（连续的）成功匹配，都对应于模式串P的一个后缀，称作“ 好后缀 ”（good suffix），若要改进BM算法，必须利用好后缀提供的“ 经验 ”。一般地，如下图的(a)和(b)所示，设本轮自右向左的扫描终止于失配位置：T[i+j] = 'X' $\ne$ 'Y' = P[j]。若分别记：

W = substr(T, i+j+1, m-j-1) = T[i+j+1, m+i)
U = suffix(P, m-j-1) = P[j+1, m)

好后缀U长度为m-j-1，故只要j <= m-2，则U必非空，且有U = W。接下来就应考虑：根据好后缀所提供的信息应如何确定，P中有哪个（哪些）字符值得与上一失配字符T[i+j]对齐，然后启动下一轮比对呢？

如上图(c)设存在一整数k，使得在将P右移j - k个单元，并使P[k]与T[i+j]相互对齐之后，P能够与文本串T的某一（包含T[m+i-1]在内的）子串匹配，亦即：P = substr(T, i+j-k, m) = T[i+k-k, m+i+j-k)。

于是，若记：V(k) = substr(P, k+1, m-j-1) = P[k+1, m-j+k)，则必然有：V(k) = W = U，也就是说，若值得将P[k]与T[i+j]对齐并做新的一轮比对，则P的子串V(k)首先必须与P自己的后缀U相互匹配。

还有另一必要条件：P中的这两自匹配子串的前驱字符不得相等，即P[k] != P[j]，否则在对齐位置也注定不会出现与P的整体匹配。若模式串P中同时存在多个满足上述必要条件的子串V(k)，则不妨选取其中最靠右者（对应于最大的k，最小的右移距离j-k），这两点都与KMP算法的处理类似。

gs[ ]表：

如上图(c)若满足上述必要条件的子串V(k)起始于P[k+1]，则模式串对应的右移量就是j-k。而k本身仅取决于模式串P以及j值，因此又可仿照KMP算法通过预处理将模式串P转换为另一张查找表gs[0, m)，其中gs[j] = j-k分别记录对应的位移量。

若P中没有任何子串V(k)可与好后缀U完全匹配，则需要从P的所有前缀中，找出可与U的某一（真）后缀相匹配的最长者，作为V(k)，并取gs[j] = m - |V(k)|。如下例是模式串P = “ICED RICE PRICE”对应的GS表，gs[5] = 12 就意味着：一旦在P[5] = 'R'处发生失配，则应将模式串P整体右移12个字符，然后继续启动下一轮比对，也可以等效地认为，以P[5-12] = P[-7]对准文本串中失配的字符，或以P[0]对准文本串中尚未对准过的最左侧字符。

下面是一个运行好后缀策略进行串匹配的实例：

整个过程中总共做10次成功的比对（黑色字符）和2次失败的比对（灰色字符），累计12次比对，文本串的每个字符，平均（12/13）不足一次。

复杂度：

同时结合BC表和GS表两种启发策略，加快模式串相对于文本串的右移速度，可以证明对于匹配失败的情况，总体比对的次数不致超过$O(n)$。若不排除完全匹配的可能，则该算法在最坏情况下的效率，有可能退化至与蛮力算法相当，所幸只要做些简单的改进，依然能够保证总体的比对次数不超过线性。综上在兼顾了坏字符与好后缀两种策略之后，BM算法的运行时间为$O(n+m)$。

4.4.gs[ ]表构造算法：

蛮力算法：

一个很直接的方法就是：对于每个好后缀P(j, m)，按照自后向前（k从j-1递减至0）的次序，将其与P的每个子串P(k ,m+k-j)逐一对齐，并核对是否出现有匹配的子串，一旦发现，对应的位移量即是gs[j]的取值。然而这里共有$O(m)$个好后缀，各需与$O(m)$个子串对齐，每次对齐后在最坏情况下需要比对$O(m)$次，因此该“算法”可能需要$O(m^3)$的时间。

MS[ ]串与ss[ ]表：

实际上构造gs[ ]表仅需线性的时间，为此需要引入ss[ ]表。如上图，对于任一整数j $\in$ [0, m)，在P[0, j)的所有后缀中，考查那些与P的某一后缀匹配者。若将其中的最长者记作MS[j]，则ss[j]就是该串的长度|MS[j]|。当MS[j]不存在时，取ss[j] = 0。综上可定义ss[j]为：

$ss[j]=\max \{ 0\le s \le j+1\,\,\,|\,\,\,P(j-s,j]=P[m-s,m) \}$

特别地，当j =m-1时，必有s = m——此时，有P(-1, m-1] = P[0, m)。如下例是模式串P = "ICED RICE PRICE"所对应的ss[]表：

由ss[ ]表构造gs[ ]表：

如下图所示，任一字符P[j]所对应的ss[j]值，可分两种情况提供有效的信息。

第一种情况如图(a)，设该位置j满足：ss[j] = j+1，即MS[j]就是整个前缀P[0,j]。此时，对于P[m-j-1]左侧的每个字符P[i]而言，对应于4.3节中图11.12(d)所示的情况，m-j-1都应该是gs[i]取值的一个候选。

第二种情况如图(b)所示，设该位置j满足：ss[j] <= j，即MS[j]只是P[0, j]的一个真后缀。同时既然MS[j]是极长的，故必有：P[ m - ss[j] -1 ] != P[ j - ss[j] ] 。这就意味着此时的字符P[m - ss[j] - 1]恰好对应于如4.3节中的图11.12(c)的情况，因此m-j-1也应是gs[m - ss[j] - 1]取值的一个候选。

反过来，根据此前的定义，每一位置i所对应的gs[i]值只可能来自与以上候选。进一步地，既然gs[i]的最终取值是上述候选中的最小（最安全者），故仿照构造bc[]表的画家算法，累计用时将不超过$O(m)$。

ss[ ]表的构造：

ss[]表是构造gs[] 表的基础与关键，若采用蛮力策略，对每个字符P[j]都做一趟扫描比对，直到出现失配，如此累计需要$O(m^2)$时间。

为了提高效率，不妨自后想前地逆向扫描，并逐一计算出各字符P[j]对应的ss[j]值。如下图所示，此时必有P[j] = P[m-hi+j-1]，故可利用此前已计算出的ss[m-hi+j-1]，分两种情况快速地导出ss[j]。在此期间，只需动态地记录当前的极长匹配后缀：P(lo, hi] = P[m -hi +lo, m)。

第一种情况如图(a)，设：ss[m - hi +j -1] <= j-lo，此时ss[m - hi +j -1]也是ss[j]可能的最大取值，于是便可直接得到：ss[j] = ss[m - hi +j -1]

第二种情况如图(b)，设：j-lo < ss[m - hi +j -1]，此时至少仍有：P(lo, j] = P[m - hi + lo, m -hi +j)，故只需将P(j - ss[m - hi + j - 1], lo] 与 P[m - hi + j - ss[m -hi + j -1], m - hi + lo)做一比对，也可确定ss[j]。当然这种情况下极大匹配串的边界lo和hi也需要相应左移。

以上构思只要实现得当，也只需$O(m)$时间即可构造出ss[]表。

算法实现：

按照以上思路，GS表的构造算法可实现如下代码：

int* buildSS ( char* P ) { //构造最大匹配后缀长度表：O(m)
   int m = strlen ( P ); int* ss = new int[m]; //Suffix Size表
   ss[m - 1]  =  m; //对最后一个字符而言，与之匹配的最长后缀就是整个P串
// 以下，从倒数第二个字符起自右向左扫描P，依次计算出ss[]其余各项
   for ( int lo = m - 1, hi = m - 1, j = lo - 1; j >= 0; j -- )
      if ( ( lo < j ) && ( ss[m - hi + j - 1] < j - lo ) ) //情况一
         ss[j] =  ss[m - hi + j - 1]; //直接利用此前已计算出的ss[]
      else { //情况二
         hi = j; lo = __min ( lo, hi );
         while ( ( 0 <= lo ) && ( P[lo] == P[m - hi + lo - 1] ) ) //二重循环？
            lo--; //逐个对比处于(lo, hi]前端的字符
         ss[j] = hi - lo;
      }
   //*DSA*/ printf ( "-- ss[] Table -------\n" );
   //*DSA*/ for ( int i = 0; i < m; i ++ ) printf ( "%4d", i ); printf ( "\n" );
   //*DSA*/ printString ( P ); printf ( "\n" );
   //*DSA*/ for ( int i = 0; i < m; i ++ ) printf ( "%4d", ss[i] ); printf ( "\n\n" );
   return ss;
}

int* buildGS ( char* P ) { //构造好后缀位移量表：O(m)
   int* ss = buildSS ( P ); //Suffix Size table
   size_t m = strlen ( P ); int* gs = new int[m]; //Good Suffix shift table
   for ( size_t j = 0; j < m; j ++ ) gs[j] = m; //初始化
   for ( size_t i = 0, j = m - 1; j < UINT_MAX; j -- ) //逆向逐一扫描各字符P[j]
      if ( j + 1 == ss[j] ) //若P[0, j] = P[m - j - 1, m)，则
         while ( i < m - j - 1 ) //对于P[m - j - 1]左侧的每个字符P[i]而言（二重循环？）
            gs[i++] = m - j - 1; //m - j - 1都是gs[i]的一种选择
   for ( size_t j = 0; j < m - 1; j ++ ) //画家算法：正向扫描P[]各字符，gs[j]不断递减，直至最小
      gs[m - ss[j] - 1] = m - j - 1; //m - j - 1必是其gs[m - ss[j] - 1]值的一种选择
   //*DSA*/ printGS ( P, gs );
   delete [] ss; return gs;
}

5.算法纵览

本文针对串匹配问题，依次介绍了蛮力、KMP、基于BC表、综合BC表与GS表等四种典型算法，其渐进复杂度的跨度范围，可概括为：

KMP算法相比于蛮力算法的优势在于无论何种情况，时间效率均稳定在$O(n+m)$，因此在蛮力算法效率接近或达到最坏的$O(nm)$时，KMP算法的优势才会十分明显。仅采用坏字符启发策略（BC）的BM算法，时间效率介于$O(nm)$至$O(n/m)$之间，其最好情况与最坏情况相差悬殊。结合了好后缀策略（BC+GS）后的BM算法，则介于$O(n+m)$与$O(n/m)$之间，其在改进最低效率的同时也保持了最高效率的优势。

单次比对成功概率：

有趣的是，单次比对成功的概率，是决定串匹配算法时间效率的一项关键因素。纵观以串匹配算法，在每一对齐位置所进行的一轮比对中，仅有最后一次可能失败：反之此前的所有比对（若的确进行过）必然都是成功的。而各种算法的最坏情况均可概括为：因启发策略不够精妙甚至不当，在每一对齐位置都需进行多达$\Omega(n)$次成功的比对，另加最后一次失败的比对。

若将单次比对成功的概率记作Pr，以上串匹配算法的时间性能随Pr的变化趋势，大致如下图所示，其中纵坐标为运行时间，分为$O(n/m)$、$O(n+m)$、$O(n*m)$三挡。（图线只是示意大致的增长趋势）由于对于同一算法，消耗于每一对齐位置的平均时间成本随Pr的提高而增加，因此计算时间与Pr都具有单调正相关的关系。

字符表长度：

实际上在所有字符均等概率出现的情况下，Pr的取值将主要决定于字符表的长度$|\sum|$，并与之成反比关系：字符越长，其中任何一对字符匹配的概率越低。在通常情况下，蛮力算法实际的运行效率并不算太低。而不同的串匹配算法也因此有各自适用的场合。