在BM算法匹配过程中,常出现模式的一部分后缀与文本匹配,而模式的前缀却不匹配,在这种情况下,就进行了一些不必要的比较。因此在BMGJ算法中,我们在对模式串与文本字符串进行匹配时采用从模式两端向中间位置交替的匹配顺序,模式匹配先从模式最右端Pm开始进行。若Pm匹配不成功,则通过Skip函数计算出模式向右移动的距离,这与BM算法中坏字符启发思想相同;若Pm匹配成功,则比较模式P1与文本中相应的字符。若P1匹配不成功,则考查文本中与模式中Pm下一个字符对齐的字符,若该字符不出现在模式中,则模式可以向右移动m 1个位置,若该字符出现在模式中,则计算其Skip函数,然后将模式向右移动相应的长度;若P1匹配成功,则按上述方法依次对Pm-1,P2,Pm-2,P3,…进行匹配,依此类推,直到匹配过程完成。实例分析:　第1次匹配:

Example

here is a simple example

第2次匹配:

Example

here is a simple example

第3次匹配(传统BM算法匹配中,此遍比较需要从右端比较5次才可以找到一个坏字符,但对于改进后的算法,只比较两次就可以找到一个坏字符):

Example

here is a simple example

第4次匹配:

Example

here is a simple example

第5次匹配:

Example

here is a simple example

在上例中,我们可以看出用传统的BM算法匹配共进行了4次移动15次比较,用改进的BM算法匹配共进行了4次移动12次比较,匹配次数减少。

改进后的BM算法的预处理时间复杂度为O(m s),空间复杂度为O(s),搜索阶段时间复杂度为O(mn)。该算法在比较右端字符失配时采用BM坏字符启发的思想,在比较了左端字符失配时采用对文本中与模式最右端对齐的下一个字符进行考查的方法,使得大多数情况下具有比BM算法更大的右移长度,从而有更好的平均性能。