BmUtils

2018-09-14  本文已影响0人  kevinfuture

package com.kevinfuture.opt.utils;

/**
 * BM算法
 * @author kevin
 * **/

public class BmUtils {

    public static void main(String[] args) {
        String test = "3rfdfgs海1贼1王0";
        System.out.println(indeOf(test, "海134贼1王"));
    }

    public static String indeOf(String source, String target) {

        char[] sourceChars = source.toCharArray();
        char[] targetChars = target.toCharArray();
        
       if(sourceChars.length < targetChars.length){
            return "";
        }

        //源字符串移动下标
        int i = targetChars.length - 1;
        //目标模式串移动下标
        int j = targetChars.length - 1;

        /**
         * 当时设计不周全,没有考虑到边界问题
         * 新增一个变量,标记是否到了结尾
         * 如果达到结尾,再次不匹配的时候,即可直接跳出
         * **/
        boolean flagOver = false;
        while(i < sourceChars.length & j > -1){
            //若相等,则从后往前移动一位继续比较
            if(sourceChars[i] != targetChars[j]){
                if(flagOver){
                    break;
                }

                /**
                 * 网上讲的内容虽然对,但是没那么复杂理解。简单来说,不管匹配不匹配,都将模式串右移
                 * 直到与模式串:
                 * 坏字符,最靠左的一个字符,匹配,不匹配则继续右移一位;
                 * 好后缀,最靠左的一个字符,匹配/部分匹配/不匹配;
                 * PS:变相来看 =》 判断模式串当前匹配位置i 左侧与右侧的长度 =》
                 * Math.max( 左侧与i值的长度; 模式串匹配,与右侧i+1位置的值匹配否,若不匹配则继续i++验证匹配否)
                 */
                int m = getBmBadChar(sourceChars[i], targetChars, j);
                int n = getBmGoodSuffix(sourceChars, targetChars, i, j);

                int len = Math.max(m,n);
                i = i + len;
                i = Math.min(i, sourceChars.length - 1);
                j = targetChars.length - 1;
                if(i + 1 == sourceChars.length){
                    flagOver = true;
                }
            }else {
                i--;
                j--;
            }
        }
        System.out.println( j + "   " + i);
        char[] chars = new char[i - j + 1];
        int y = 0;

        for(int x = i + 1; x < i + j; x++ ){
            chars[y++] = targetChars[x];
        }
        return String.valueOf(chars);
    }

    /**
     * 粘自阮一峰老师的博客:
         (1)"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀,则它的位置以"F"为准,即5(从0开始计算)。
       (2)如果"好后缀"在搜索词中只出现一次,则它的上一次出现位置为 -1。比如,"EF"在"ABCDEF"之中只出现一次,则它的上一次出现位置为-1(即未出现)。
       (3)如果"好后缀"有多个,则除了最长的那个"好后缀",其他"好后缀"的上一次出现位置必须在头部。比如,假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B",请问这时"好后缀"的上一次出现位置是什么?
            回答是,此时采用的好后缀是"B",它的上一次出现位置是头部,即第0位。这个规则也可以这样表达:如果最长的那个"好后缀"只出现一次,则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB",
            即虚拟加入最前面的"DA"。
     * 好后缀
     * n:模式串索引位置
     * i:好后缀索引位置
     * **/
    private static int getBmGoodSuffix(char[] sourceChars, char[] targetChars, int i, int j){
        int n = 0;
        for(; n < j; n++){
            while(i < sourceChars.length){
                if(targetChars[n] == sourceChars[i++]){
                    n++;
                }else{
                    n = 0;
                }
            }
        }
        return j - n;
    }
    /**
     * 坏字符
     * @return 返回的是匹配值对应的下标序号
     * **/
    private static int getBmBadChar(char sChar, char[] targetChars, int j){
        int m = j;
        for(; m >= 0; m--){
            if(targetChars[m] == sChar){
                return j - m;
            }
        }
        return j + 1;
    }
}

PS:尚有些问题,需要调整;坏字符、好后缀获取的没有问题

上一篇 下一篇

猜你喜欢

热点阅读