主要思想 坏字符试探 从右向左比 革您字奔箬忠安數 Bad character heuristics 第一个字符不匹配 革 0123456789 且目标串的第一个字符在模式串的其它 abbadia baba 位置出现,在这种情况下,模式串右移 模式串 ba bac 到其相应字符与目标串第一个字符匹配 babac 的位置上。 示例 Good suffix heuristics 位置0123456789 位置0123456789 目标串 a bb a b ab acba 目标串 a b a ab cba 模式串 b a b ac 模式串 c a b a b b a b a c c a b a b 导致不匹配,但目标串字符b出现在模 目标串和模式串的后缀ab已匹配,模 其最右边的字符b和目标串的第一个字 式串应当右移2位,使其从右至左的第 符b匹配 个子串ab与目标串的后缀ab匹配 Good suffix heuristics Good suffix heuristics 下面这个例子中,同样目标串和模式 目标串和模式串的后缀bab已匹配,在位置 串的后缀ab已匹配,但子串ab没有在模 有再出现在 式串的其它位置出现。所以模式串可以 右移5位 位置0123456789 bab)的后缀匹配 位置0123456789 目标串 ab c a cba 目标串 aa b a b a cba 模式串cbaa 模式串 a bb a b cb a ab a bb a b7 37 主要思想 从右向左比： 当目标串中的字符根本就没有在模式串中出现，模 式串就可以从这一字符开始向右移动m位置数。 例子：位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a b b a d a b a c b a 模式串 b a b a c b a b a c 这种算法最好的情况就是模式串每一次和目标串比 较，它们第一个字符就不匹配，且目标串中的字符不 在模式串中出现，这样模式串每一次都可移动m位。 38 坏字符试探 Bad character heuristics 目标串和模式串第一个字符不匹配， 且目标串的第一个字符在模式串的其它 位置出现，在这种情况下，模式串右移 到其相应字符与目标串第一个字符匹配 的位置上。 39 示例 位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a b b a b a b a c b a 模式串 b a b a c b a b a c b-c导致不匹配，但目标串字符b出现在模 式串的位置0和位置2，于是模式串可右移2 位，使其最右边的字符b和目标串的第一个字 符b匹配。 40 Good suffix heuristics 位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a b a a b a b a c b a 模式串 c a b a b c a b a b √ 目标串和模式串的后缀ab已匹配，模 式串应当右移2位，使其从右至左的第二 个子串ab与目标串的后缀ab匹配。 41 Good suffix heuristics 下面这个例子中，同样目标串和模式 串的后缀ab已匹配，但子串ab没有在模 式串的其它位置出现。所以模式串可以 右移5位。 位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a b c a b a b a c b a 模式串 c b a a b c b a a b 42 Good suffix heuristics 目标串和模式串的后缀bab已匹配，在位置 1出现a-b不匹配，同时子串bab也没有再出现在 模式串中，但在这种情形下模式串不能象上一 种情形右移5位，而只能右移3位，因为模式串 的前缀ab和子串bab（也就是目标串的子串 bab）的后缀匹配。 位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a a b a b a b a c b a 模式串 a b b a b a b b a b