BM（Boyer-Moore）目前被认为最高效的字符串搜索算法

坏字符算法

BM使用的式从右往左的匹配模式,在进行匹配时,先从最后一个字符进行匹配,如:

坏字符算法

在上面的例子中,在第一次匹配中,从右开始第一个d与f不匹配,一般情况下是往右移动一位,但在BM中,进行启发式规则的匹配,f不属于pattern所以整个启发式往右移动4个位置,再进行预处理,发现d与b不匹配,再次进行移动,使得最右边中的b与txt中的b对其.这样能够更快速的进行匹配.在txt中红色的字符就是所谓的坏字符:

当出现一个坏字符时,将模式中最靠右的对应字符与坏字符相对,然后继续匹配(这个最靠右的字符应该是位于坏字符前面的pattern,否则的话pattern会变成向左移动),当pattern中不存在坏字符时,直接移动pattren长度的距离

 public int [] BMbc(String pattern){
        int length = pattern.length();
        int [] arr = new int [256];
      byte [] bytes = pattern.getBytes();
        for(int i=0;i<256;i++){
            arr[i] = bytes.length;
        }
        
        for (int i=0;i<bytes.length;i++){
            arr[bytes[i]+128] = bytes.length-1-i;
        }
        return arr;
    }

好后缀算法

在匹配过程中,如果匹配了一个好后缀(也就是在pattern的后面有几位数是匹配到的),而接下来的一个字符不匹配,在这个pattern的前面拥有子串和好后缀完全匹配的,则将最靠右的字串移动到好后缀的位置进行匹配.如果找不到与好后缀匹配的字串,那么直接移动整个模式串

子串匹配好后缀

子串无法匹配好后缀

在好后缀算法中,先对模式进行预处理获取辅助数组,suff[i]就是求pattern中以i位置字符为后缀和以最后一个字符为后缀的公共后缀串的长度

public void getSuff(char [] chars,int [] suff){
       int length = chars.length;
           //从右边第二个字符开始进行匹配
       for(int i=length-2;i>=0;i--){
           int j = i;
           while (j>=0&&chars[j] == chars[length-1-i+j])
           //chars[i]与char[length-1]开始进行匹配,相同则移动到下一位
               j--;
           suff[j] = i-j;//i表示的是子字符的起点,j表示的相同字符结尾,i-j表示的就是匹配的长度
       }
   }

这里bmGs[]的下标是数字而不是字符了，表示字符在pattern中位置。
如前所述，bmGs数组的计算分三种情况，与前一一对应。假设图中好后缀长度用数组suff[]表示。
Case1：遍历到j字符时无法匹配的一般情况在模式的后面有着能够匹配好后缀的子串，如下图，j是好后缀之前的那个位置。从图片中可以看到,对于好后缀的长度由suff[i]获得,而此时可以计算出bmGs[j]=m-1-i,而j的位置j=m-1-suff[i]从而任意的i有bmGs[m-1-suff[i]] = m-1-i;

引用百度图片case1

Case2：在匹配到好后缀的子串的同时,子串是模式中最后的字符串：当子串刚好是字符串中最后的字符时,也就是当suff[i]=i+1这时候位于0与m-1-suff[i]之间的字符无法匹配时,他们的移动距离都是m-1-i如下图所示：

引用百度图片case2

Case3：好后缀在模式后面没有匹配，直接将整个模式移动m距离,bmGs[i] = strlen（pattern）= m

引用百度图片case3


    //好后缀算法中:获取以数组suff,其中suff[i]表示以chars[i]为结尾的字符串与整个字符串之间相同的字符长度.
    public void getSuff(byte [] bytes,int [] suff){
        int length = bytes.length;
        suff[length-1] = length;
        for(int i=length-2;i>=0;i--){
            int j = i;
            while (j>=0&&bytes[j] == bytes[length-1-i+j])//chars[i]与char[length-1]开始进行匹配,相同则移动到下一位
                j--;
            suff[i] = i-j;//i表示的是子字符的起点,j表示的相同字符结尾,i-j表示的就是匹配的长度
        }
    }

    //好后缀算法,获取移动数组
    public int [] BMgs(String pattern){
        //获取模式的byte数组
        byte [] bytes = pattern.getBytes();
        //获取模式长度
        int length = bytes.length;
        //构建移动数组
        int [] arr = new int [length];
        //构建辅助数组
        int [] suff = new int [length];
        //获取辅助数组
        getSuff(bytes,suff);
        //遍历整个数组
        //对不在好后缀的长度都设置为length 包括case3
        for(int i=0;i<length;i++){
            arr[i] = length;
        }
        //对case2的情况进行处理
        int j=0;
        for(int i=length-1;i>=0;i--){
            if (i+1==suff[i]){
                for(;j<=length-1-suff[i];j++){
                    if(length==arr[j])
                    arr[j] = length-1-i;
                }
            }
        }
        //对case1进行处理
        for(int i=0;i<length-1;i++){
            arr[length-1-suff[i]] = length-1-i;
        }
        return arr;
    }

BM同时通过这两种方法对字符串进行搜索

public int BM(String txt,String pattern){

        byte [] bytes = txt.getBytes();

        byte [] patternbyte = pattern.getBytes();
        if(bytes.length<patternbyte.length)
            return -1;
        int [] arrBMbc = BMbc(pattern);

        int [] arrBMgs = BMgs(pattern);
        int i=0;
        while (i<bytes.length-patternbyte.length){
            int j=patternbyte.length-1;
            for(;j>=0;j--){
                if(bytes[i+j]!=patternbyte[j])
                    break;
            }
            if(j<0)return i;
            i+=Math.max(arrBMbc[bytes[i+j]+128]-patternbyte.length+1+i,arrBMgs[j]);
        }

        return -1;
    }