BM算法.ppt

文档介绍：BM 算法 Boyer – Moore Scans the pattern from right to left. P495 Example 一、问题与思路提示 1 从后向前,比较模板与正文 1、若在比较的过程中,模板最后一位与文本相应位置处的字符不相等,且: (1)若该文本字符在模板中不出现,则可以把模板从左向右滑动 m个字符。(2)若该文本字符在模板中出现, 所有“出现”元素中的最后一个位于模板 m字符中的第 k个,则可以把模板从左向右滑动 m-k 个位置,与文本相应的字符 line up , 这样保证不会产生遗漏。本例中,只用了 18次比较,而其它算法则需要 41次比较。对模板中出现的不同字符, P497 程序用于求其出现在模板中的最后一个位置。提示 2 如果最后一位与文本相应位置处的字符相等,则模板与正文指针各向左前移一位, 继续比较,直到遇到不相等, 此时有多个位相等。模板向右 slide 几个位置呢? P497 例 设?k,r, ,r<k ,使: p r+1, …,p r+m-k 与p k+1,…,p m相等式且p k?p r(*) 则对齐 p k+1,…,p m与p r+1, …,p r+m-k 就可能形成匹配,匹配字符个数为 m-k 。为了不遗漏任何可能的匹配,则 r是满足( *)模板序列中最大的 r。 MatchJump [k]= slide[k] +m-k, 1 ?k?m 其中: 1、slide[k] 是在 p k+1位置不等时, line up 使 p k+1,…,p m与p r+1, …,p r+m-k 对齐时,模板向右滑动的长度; 2、 m-k 指从后向前比较时,连续相等的元素有 m-k 个。 3、MatchJump [k] 是下一次从后开始向前比较时正文指针所在的位置。如果存在这样的 r is the largest index, 使: p k+1,…,p m与p r+1, …,p r+m-k 相等要不遗漏任何可能的匹配,则对齐 p k+1,…,p m 与p r+1, …,p r+m-k ,则模板需要滑动 m-(r+m- k)= k-r 个位置,则: Slide[k]=k-r