JAVA代码实现 BF 算法的改进算法：KMP 算法和 BM 算法

KMP算法和BM算法是两种常用的字符串匹配算法。

KMP算法的思想是，当出现不匹配时，已经匹配过的前缀中一定有一部分是可以直接跳过的，不需要重新匹配。通过预处理模式串，得到一个next数组，用于记录模式串中每个前缀的最长可匹配前缀长度。在匹配时，当文本串中出现不匹配字符时，根据next数组可以直接跳过一部分已经匹配过的前缀，从而提高匹配效率。

KMP算法的JAVA代码实现如下：

public class KMP {
    public static int kmp(String text, String pattern) {
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < text.length() && j < pattern.length()) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == pattern.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    private static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
}

BM算法的思想是，在匹配过程中尽可能地多跳过一些字符，从而提高匹配效率。它的核心是两个规则：坏字符规则和好后缀规则。坏字符规则用于处理文本串和模式串不匹配的情况，好后缀规则用于处理文本串和模式串匹配的情况。

BM算法的JAVA代码实现如下：

public class BM {
    public static int bm(String text, String pattern) {
        int[] bc = generateBC(pattern);
        int[] suffix = new int[pattern.length()];
        boolean[] prefix = new boolean[pattern.length()];
        generateGS(pattern, suffix, prefix);
        int i = 0, j = 0;
        while (i <= text.length() - pattern.length() + j) {
            for (j = pattern.length() - 1; j >= 0; j--) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j < 0) {
                return i;
            }
            int x = j - bc[(int) text.charAt(i + j)];
            int y = 0;
            if (j < pattern.length() - 1) {
                y = moveByGS(j, pattern.length(), suffix, prefix);
            }
            i = i + Math.max(x, y);
        }
        return -1;
    }

    private static int[] generateBC(String pattern) {
        int[] bc = new int[256];
        for (int i = 0; i < 256; i++) {
            bc[i] = -1;
        }
        for (int i = 0; i < pattern.length(); i++) {
            int ascii = (int) pattern.charAt(i);
            bc[ascii] = i;
        }
        return bc;
    }

    private static void generateGS(String pattern, int[] suffix, boolean[] prefix) {
        int len = pattern.length();
        for (int i = 0; i < len; i++) {
            suffix[i] = -1;
            prefix[i] = false;
        }
        for (int i = 0; i < len - 1; i++) {
            int j = i;
            int k = 0;
            while (j >= 0 && pattern.charAt(j) == pattern.charAt(len - 1 - k)) {
                j--;
                k++;
                suffix[k] = j + 1;
            }
            if (j == -1) {
                prefix[k] = true;
            }
        }
    }

    private static int moveByGS(int j, int len, int[] suffix, boolean[] prefix) {
        int k = len - 1 - j;
        if (suffix[k] != -1) {
            return j - suffix[k] + 1;
        }
        for (int r = j + 2; r <= len - 1; r++) {
            if (prefix[len - r]) {
                return r;
            }
        }
        return len;
    }
}