字符串匹配算法 - BM 算法

介绍查看：BM算法漫画介绍

BM算法的要点：“坏字符”+“好后缀”。

坏字符含义：

1. 如果出现了“坏字符”，就找未匹配的模式串左侧最靠右的首个和“坏字符”相等的字符，然后挪过去
2. 如果只是依赖“坏字符”原则，其实已经可以减少很多无效匹配了。但如果出现下图所示的情况，每次还是只移动一位，所以我们接下来可以再进行一个“好后缀”的原则匹配。
   
   “好后缀”概念：主串的子串和模式串中都有共同的后缀“GCG”，这个就是好后缀。
   如果此时发现模式串的其他位置anotherPlace还有好后缀，那么就可以挪动模式串，直接将anotherPlace和主串的好后缀对齐，就可减少比较次数
   
   假如模式串中不存在anotherPlace，那么就在模式串的前缀中找是否有和“好后缀的后缀”相等的字符串，然后进行移动（这个就比较像KMP算法了）
   现在我们已经知道什么是“坏字符”，什么是”好前缀“。那么我们怎么判断什么时候用坏字符规则，什么时候用好前缀规则呢？
   答案很简单，直接每一轮分别按照两种规则计算相应的挪动距离，哪个距离长，就挪动相应的长度。

附上RK算法的代码和BM算法的简单版本

// RK算法

    public static int rabinKarp(String str,String pattern) {

//主串长度

        int m = str.length();

//模式串的长度

        int n = pattern.length();

//计算模式串的hash值

        int patternCode = hash(pattern);

//计算主串当中第一个和模式串等长的子串hash值

        int strCode = hash(str.substring(0, n));

//用模式串的hash值和主串的局部hash值比较。

//如果匹配，则进行精确比较；如果不匹配，计算主串中相邻子串的hash值。

        for(int i = 0; i < m - n + 1; i++) {
            if (strCode == patternCode && compareString(i, str, pattern)) {
                return i;
            }

//如果不是最后一轮，更新主串从i到i+n的hash值

            if (i < m - n) {
                strCode = nextHash(str, strCode, i, n);
            }
        }
        return -1;
    }

    private static int hash(String str) {

        int hashcode =0;

//这里采用最简单的hashcode计算方式：

//把a当做1，把b当中2，把c当中3.....然后按位相加

        for(int i =0; i < str.length(); i++) {
            hashcode += str.charAt(i) - 'a';
        }

        return hashcode;
    }

    private static int nextHash(String str,int hash,int index,int n) {
        hash -= str.charAt(index) - 'a';
        hash += str.charAt(index + n) - 'a';

        return hash;
    }

    private static boolean compareString(int i,String str,String pattern) {

        String strSub = str.substring(i, i + pattern.length());

        return strSub.equals(pattern);
    }

	public static void main(String[] args) {

        String str = "aacdesadsdfer";

        String pattern = "adsd";

        System.out.println("第一次出现的位置:" + rabinKarp(str, pattern));
    }

 //在模式串中，查找index下标之前的字符是否和坏字符匹配
    private static int findCharacter(String pattern, char badCharacter, int index) {

        for (int i = index - 1; i >= 0; i--) {
            if (pattern.charAt(i) == badCharacter) {
                return i;
            }
        }

//模式串不存在该字符，返回-1

        return -1;
    }


    public static int boyerMoore(String str, String pattern) {

        int strLength = str.length();

        int patternLength = pattern.length();

//模式串的起始位置

        int start = 0;

        while (start <= strLength - patternLength) {
            int i;
            //从后向前，逐个字符比较
            for (i = patternLength - 1; i >= 0; i--) {
                if (str.charAt(start + i) != pattern.charAt(i))
//发现坏字符，跳出比较，i记录了坏字符的位置
                    break;
            }

            if (i < 0) {
//匹配成功，返回第一次匹配的下标位置
                return start;

            }
//寻找坏字符在模式串中的对应
            int charIndex = findCharacter(pattern, str.charAt(start + i), i);
//计算坏字符产生的位移
            int bcOffset = charIndex >= 0 ? i - charIndex : i + 1;
            start += bcOffset;

        }

        return -1;
    }


    public static void main(String[] args) {

        String str = "GTTATAGCTGGTAGCGGCGAA";

        String pattern = "GTAGCGGCG";

        int index = boyerMoore(str, pattern);

        System.out.println("首次出现位置：" + index);
    }