正文text：bu模式pattern：au图2.2 失配时的情况
shift函数通过对已经匹配部分的考查决定模式右移的长度，失配发生时，如果u在模式中再次出现且前缀不是a字符（例如c字符），则将模式串右移使得正文中的u与满足上述条件的最右边的u对齐。如图2.3所示，如果u在模式中没有再次出现或者再次出现但前缀是a字符，则不能按照上述方法右移。如果模式存在一个前缀v，该v也是u的后缀，那么找到这样一个最长的v，将模式串右移，使模式前缀v与正文中u的后缀v对齐，如图2.4所示，在极端情况下，不存在这样的v，模式串将跳过u。
正文text：bushift模式pattern：au模式pattern：cu
图2.3 shift的第一种情况
正文text：bushift模式pattern：au模式pattern：v
图2.4 shift的第二种情况
skip函数需要考查造成失配的正文字符（此时为b）在模式中出现的情况，如果b在模式中存在，则右移模式使正文b与模式中最右边的b对齐。如图2.5所示，如果b在模式中不出现，则将模式右移跳过字符b，如图2.6所示。注意skip有可能是负值，因此在移动模式的时候，BM算法选取shift和skip的最大值。
正文text：buskip模式pattern：au模式pattern：b不包含b
图2.5 skip的第一种情况
正文text：buskip模式pattern：au模式pattern：不包含b
图2.6 skip的第二种情况
下面给出Boyer-Moore算法： Algorithm BM k = m-1;
while (k < n) {
j = m-1;
while((j >= 0)&&(pat[j] == text[k] )) { j --; k--; }
if (j == -1) then match found at taxt[k] else k=k+max (skip[ text [k] ], shift[k]) }
no match found
例子2：
1. which- f inally-halts --at-that-point at-that (f not in pattern)
2. which-finally - halts --at-that-point at-that (- in pattern)
3. which-finally-ha l ts --at-that-point at-that (l not in pattern) 4.which-finally-halts --at -that-point at-that
5. which-finally-halts --at-that-point at-that
skip数组对于字符空间较小的情况效果并不显著，但当字符空间很大而模式串较短时，例如字符空间为ASC II表时，将变得非常有效。BM算法的平均时间复杂度为O(n/m)。
BM 算法采用“跳跃式”查找策略，因此该算法在比较字符的次数上比传统的模式匹配算法少，因此在入侵检测系统中得到了广泛的应用。在模式匹配中存在两个基本定理：任何字符串匹配算法在最坏情况下必须检查至少n-m+1个文本中的字符；任何字符串匹配算法至少检查n/m个字符。因此，没有一个算法比BM算法有更好的计算复杂度。但是我们可以通过改进来减少比较次数，提高匹配的平均性能。
2.4 BMH算法
BM算法为了确定在不匹配的情况下最大的可移位距离而是用了两种启发，即“坏字符”启发和“好后缀”启发，两种启发均能导致最大为m的移动距离。但是，忧郁“好后缀”启发的预处理和计算过程都比较复杂，Horspool于1980年发表了改进与简化BM算法的论文，即Boyer-Moore-Horspool（BMH）算法[9]。BMH算法在移动模式时仅考虑了“坏字符”策略。它首先比较文本指针所指字符和模式串的最后一个字符，如果相等再比较其余m-1个字符。无论文本中哪个字符造成了匹配失败，都将由文本中和模式串最后一个位置对应的字符来启发模式向右的移动。即当匹配开始比较text[k-m+1?k]和pattern[0?m-1]时，从右至左依次检查text[k]，text[k-1]?text[k-m+1]，一旦发现不匹配，就将文本指针重新赋值为k+skip[text[k]](k是一个中间变量，表示文本中每次从右至左开始比较的起始位置)。
关于“坏字符”启发和“好尾缀”启发的对比，在文献[5]中的研究表明：“坏字符”启发在匹配过程中占主导地位的概率为94.03%，远远高于“好尾缀”启发。在一般情况下，BMH算法比BM有更好的性能，它简化了初始化过程，省去了计算“好尾缀”启发的移动距离，并省去了比较“坏字符”和“好尾缀”的过程。算法将失配与计算右移量独立，计算右移量时并不关心正文中哪个字符
造成了失配，而是简单的使用正文中与模式最右端字符对齐的字符来决定右移量，即只使用skip数组。
BMH算法的具体描述如下： Algorithm BMH
for (i=0;i for ( i =0;i j=m-1; while ((j>=0)&&(pat[j]==text[k])) { j--; k--; } if ( j= =-1) then match found at text[k] else k=k+skip[text[k]] } no match found 例子3： 1. astring s earchingexamplienvolingrelatively relative (s not in pattern) 2. astringsearchin g examplienvolingrelatively relative (g not in pattern) 3. astringsearchingexampl i envolingrelatively relative (i in pattern) 4．astringsearchingexamplie n volingrelatively relative (n not in pattern) 5．astringsearchingexamplienvoling r elatively relative (r in pattern) 6．astringsearchingexamplienvolingrelatively relative 根据BMH算法我们再以text=‘abhdgfdabbdbdabdbfd’，pattern=‘abdbfd’字串为例，开始匹配时，把模式串与正文自左边对齐。使用BMH算法经过6次循环后匹配成功。当字符集元素个数为s时，BMH算法预处理时间复杂度为O(m + s)，空间复杂度为O(s)。BMH算法在最好的情况下的复杂度是O（n/m），最坏的情况下的复杂度为O(m n )，但在一般情况下比BM有更好的性能。它只使用了一个数组，简化了初始化过程，省去了求最大值的计算。 匹配过程如表2.1所示： 表2.1 BMH算法匹配过程 文本 a b h d g f d a b b d b d a b d b f d 指针移动 1. a b d b f d skip[?f?]=1 2. a b d b f d skip[?d?]=3 3. a b d b f d skip[?b?]=2 4. a b d b f d skip[?b?]=2 5. a b d b f d skip[?a?]=5 6. a b d b f d BMH算法在一般情况下由于省去了求最大值的计算，因而比BM有更好的性能。 2.5 BMHS算法 1990年，Sunday在BMH算法的基础上又提出了改进，提出了BMHS算法[10],其主要改进思想是：在计算skip数组时，考虑下一个字符的情况，即利用下一个字符决定右移量。若下一个字符不出现在模式中，BMHS算法的右移量比BMH算法的大，若text[i]不出现在模式中，而text[i+1]出现在模式中时，则BMHS算法效果不如BMH算法，但在通常情况下BMHS算法实现速度大于BMH算法，它在最好情况下的时间复杂度为O(n/m+1)。 BMHS算法如下： Algorithm BMHS for (i=0;i skip[i]=m+1; for (i=0 ;i j=m-1; While((j>=0)&&(pat[j]= =text[k+j-(m-1)])) { j- -; } if(j==-1) then match found at text[k] else k=k+skip[text[k+1]]