小例子-理解高效BM算法字符串如何比较是否相等

字符串比较非常好理解，比如有一个字符串"abcacabdc" ，我们需要查找里边是否包含"abd"这个字符串

我们把"abcacabdc" 分别放到主数组中，把"abd"放到查找数组中如下图所示。

 

 

好了只要我们用一个循环一次次比较，一次次位移就可以。 比如 abc 先和abd比较 一个一个字符比较 然后 在bca和abd,依次类推。

我们看一下代码，可以跑一下

注意：这里边我们正常应该是把字符串放到一个字符串数组中，但是我们没有这样做，而直接用字符串charAt()方法道理一样。

应该放到字符数组中比较合适。

  public static void main(String[] args) {
        String leadstr = "abcacabdc";
        String target = "abd";
        System.out.println(indexOf(leadstr, target));

    }

    /**
     * 构建一个散列表256位的包括所有字母的ASCII字母
     */
    private static final int ASCIISIZE = 256;

    static int indexOf(String leadstr, String target) {
        int leadLeng = leadstr.length();
        int targetLeng = target.length();
        int moveCount = leadLeng - targetLeng;
        int i = 0;
        while (i <= moveCount) {
            int targetLast = targetLeng - 1;
            int j;
            for (j = i + targetLeng - 1; j >= i; j--) {
                char lead = leadstr.charAt(j);
                char tar = target.charAt(targetLast--);
                if (lead != tar) {
                    break;
                }
            }
            ;
            if (targetLast <0)return i;//匹配成功
            i++;
        }
        return -1;
    }

我们采用以上这总办法，每次比较都需要比较int count = leadstr.length() - target.length() + 1; 次但是有没有办法我们尽量少比较次数提高效率。

我们看一下，第一次比较，你发现没，主数组 下标为2的字符c在，查找数组中没有，所以我们跳过中间直接到，主数组下标为3的a开始，如下图所示

 

跳到之后我们还是和之前一样，我们还是从后往前比较主数组下标5,a 和 查找数组2，d比较发现不等，这个时候我们把

a,在查找数组中遍历一下，发现查找数组也有a在 0号位，所以我们继续跳

如图所示，我们跳到，主数组5 和查找数组0对齐的位置。没有必要在对比一次主数组下标为4的情况因为一定不相等。

只有这样才符合 字符相等的情况，你自己体会一下。

所以我们改进一下代码。

    public static void main(String[] args) {
        String leadstr = "abcacabdc";
        String target = "abd";
        System.out.println(indexOf(leadstr, target));

    }

    /**
     * 构建一个散列表256位的包括所有字母的ASCII字母
     */
    private static final int ASCIISIZE = 256;

    static int indexOf(String leadstr, String target) {
        int leadLeng = leadstr.length();
        int targetLeng = target.length();
        int moveCount = leadLeng - targetLeng;

        int i = 0;
        int[] bc = new int[ASCIISIZE];
        charOfIndex(target, bc);
        while (i <= moveCount) {
            int targetLast = targetLeng - 1;
            int j;
            char lead = 0;
            char tar = 0;
            for (j = i + targetLeng - 1; j >= i; j--) {
                lead = leadstr.charAt(j);
                tar = target.charAt(targetLast--);
                if (lead != tar) {
                    break;
                }
            }
            ;
            if (targetLast < 0) return i;//匹配成功
            int xi = bc[(int) lead];
            if (xi < 0) i = i + targetLeng;//如果返回了-1表示不存在，直接跳过target.length()长度
                //如果存在那我们就跳过(si = j) - xi位 
            else i = j - xi;
        }
        return -1;
    }

    /**
     * 构建一个散列表为了方便找到一个字符是否在一个字符串中出现过
     *
     * @param str
     * @param bc
     */
    private static void charOfIndex(String str, int[] bc) {
        for (int i = 0; i < ASCIISIZE; i++) {
            bc[i] = -1;//赋值
        }
        for (int i = 0; i < str.length(); i++) {
            int asci = (int) str.charAt(i);//将字符转换成ASCII码
            bc[asci] = i;//记录一下 下标号到散列表中
        }
    }