算法5.7 Boyer-Moore字符串查找

算法描述

  • BM查找是在允许回退时,从右向左扫描pat检查是否与txt匹配,并在匹配失败时通过跳跃将文本中字符和它在pat中出现的最右位置对齐

实现

  • 跳跃表right[]:该数组记录字母表中每个字符在pat中最靠右出现的位置,当不存在记为-1,该记录表示当匹配失败时pat应该向右跳跃几位
  1. public BoyerMoore(String pat){
  2.     this.pat = pat;
  3.     int R = 256;
  4.     int M = pat.length();
  5.     right = new int[R];
  6.     for (int c = 0; c < R; c++)
  7.         right[c] = -1;
  8.     for (int j = 0; j < M; j++)
  9.         right[pat.charAt(j)] = j;
  10. }

right.png

  • 查找:i,j分别为txt和pat指针,若j从M-1到0循环,txt.charAt(i+j)和pat.charAt(j)都相等,则匹配成功,否则失败
    • 失败字符不在pat中:则将pat右移j+1位(通过i增加j+1实现),重置j为M-1
    • 失败字符在pat中:则将pat右移直到该字符和其在pat中最右边位置对齐
    • 当需要左移时:至少让i+1,右移一位
  1. public int search(String txt){
  2.     int N = txt.length();
  3.     int M = pat.length();
  4.     int skip;
  5.     for (int i = 0; i < N; i += skip){
  6.         skip = 0;
  7.         for (int j = M-1; j >= 0; j--){
  8.             if (txt.charAt(i+j) != pat.charAt(j)){
  9.                 skip = j - right[txt.charAt(i+j)];
  10.                 if (skip < 1) skip = 1;
  11.                 break;//当前字符匹配失败
  12.             }
  13.         }
  14.         if (skip == 0) return i;//找到匹配
  15.     }
  16.     return N;//匹配失败
  17. }

BM.png

  1. public class BoyerMoore {
  2.     private int[] right;
  3.     private String pat;
  4.     public BoyerMoore(String pat){}
  6.     public int search(String txt){}
  7. }

算法分析

  • 长N的txt和M的pat,是哟BM算法需要~N/M次比较

证明:跳跃使得几乎所有比较都会跳过M个字符