数据结构与算法 – 单模式字符串匹配算法（BF、RK、KMP、BM）

/**
 * 字符串暴力匹配算法
 * @param text 主串
 * @param pattern 模式串
 */
public static int bf(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    if (n < m) {return -1;}
    // i表示主串与模式串对齐的第一个字符
    int i = 0;
    while (i <= n - m) {
        int j;
        // 模式串从后往前匹配
        for (j = 0; j <= m-1; ++j) {
            if (text.charAt(i+j) != pattern.charAt(j)){
                break; // j为已匹配的字符串下一个字符的下标
            }
        }
        if (j == m) {
            // 匹配成功，返回主串与模式串第一个匹配的字符的位置
            return i;
        }
        i += 1;
    }
    return -1;
}

/**
 * Rabin-Karp算法
 * @param text 主串
 * @param pattern 模式串
 */
public static int rk(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    if (n < m) { return -1; }
    // 对模式串与第一个字串求哈希值
    Integer patternCode = pattern.hashCode();
    String sub = text.substring(0, m);
    int subCode = sub.hashCode();
    // 对主串中的n-m+1个子串分别求哈希值
    int i = 0;
    while (i < n - m + 1) {
        // 哈希值相同，才进一步确认
        if (patternCode.equals(subCode) && sub.equals(pattern)) {
            return i;
        }
        // 继续下一个子串
        i++;
        sub = text.substring(i, i + m);
        subCode = sub.hashCode();
    }
    return -1;
}

/**
 * 实现next()函数
 * @param pattern 模式串
 */
private static int[] kmpNext(String pattern){
    int m = pattern.length();
    // 声明部分匹配表数组 next，用于存储部分匹配值
    int[] next = new int[m];
    // 第一个字符没有前后缀，最长匹配值为 0
    next[0] = 0;
    // 循环模式串，计算部分匹配表，i初始化为 1
    // j用于记录部分匹配值
    for(int i = 1,j = 0; i < m; i++){
        // ④ 在0~i中，j>0 并且 pattern.charAt(j) != pattern.charAt(i)时，
        //   表示上一轮比较，前后缀部分匹配值为j。
        //   上一轮比较时，下标[0~j-1]是前后缀最长相同字符串。
        //   下标[j-1]的部分匹配值表示为next[j-1]，即j=next[j-1];
        while(j > 0 && pattern.charAt(j) != pattern.charAt(i)){
            j = next[j - 1];
        }
        // ① 在0~i中，j=0 并且 pattern.charAt(j) != pattern.charAt(i)时，
        //   表示前后缀字符串集合中没有相同字符串，next[i]=j（同next[i]=0）
        // ② 在0~i中，j=0 并且 pattern.charAt(j) == pattern.charAt(i)时，
        //   表示前后缀字符串集合中有 1 个相同字符串，j++;next[i]=j;（同next[i]=1）
        // ③ 在0~i中，j>0 并且 pattern.charAt(j) == pattern.charAt(i)时，
        //   表示上一轮比较，前后缀部分匹配值为j。这轮为j+1。因此j++;next[i]=j;
        if(pattern.charAt(i) == pattern.charAt(j)){
            j++;
        }
        next[i] = j;
    }
    return next;
}

public static int kmp(String text, String pattern){
    int n = text.length();
    int m = pattern.length();
    if (n < m) { return -1; }
    // 计算出部分匹配表
    int[] next = kmpNext(pattern);
    // i表示主串与模式串对齐的第一个字符
    int i = 0;
    while (i <= n - m) {
        int j;
        // 模式串从后往前匹配
        for (j = 0; j <= m-1; ++j) {
            if (text.charAt(i+j) != pattern.charAt(j)){
                break; // j为已匹配的字符串下一个字符的下标
            }
        }
        if (j == m) {
            return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
        }
        int s = 1;
        if (j > 0) {
            // 后移位数 = 已匹配的字符数j - 对应的部分匹配值next[j-1]
            s = j - next[j-1];
        }
        i += s;
    }
    return -1;
}

public static int bm(String text, String pattern){
    int n = text.length();
    int m = pattern.length();
    if (n < m) { return -1; }
    // 计算 坏字符规则表，记录模式串中每个字符最后出现的位置
    Map<Character, Integer> badCharRules = generateBadCharRules(pattern);
    // 计算 好后缀规则表，记录好后缀位置对应后移的位数
    int[] goodSuffixRules = generateGoodSuffix(pattern.toCharArray());
    // i表示主串与模式串对齐的第一个字符
    int i = 0;
    while (i <= n - m) {
        int j;
        // 模式串从后往前匹配
        for (j = m - 1; j >= 0; --j) {
            if (text.charAt(i+j) != pattern.charAt(j)){
                break; // 坏字符对应模式串中的下标是j
            }
        }
        if (j < 0) {
            // 匹配成功，返回主串与模式串第一个匹配的字符的位置
            return i;
        }
        // 后移位数 = 坏字符(对应模式串)的位置 - 坏字符在模式串中最后出现位置
        int s1 = j - getBadCharPosition(badCharRules, text.charAt(i + j));
        // 好后缀后移位数
        int s2 = goodSuffixRules[j];
        //后移这两个规则之中的较大值
        i += Math.max(s1, s2);
    }
    return -1;
}

/**
 * 坏字符规则表
 * 记录模式串中每个字符最后出现的位置
 */
private static Map<Character, Integer> generateBadCharRules(String pattern) {
    Map<Character, Integer> bmBc = new HashMap<>(pattern.length());
    // 选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过
    for (int j = 0; j < pattern.length(); j++) {
        bmBc.put(pattern.charAt(j), j);
    }
    return bmBc;
}
/**
 * 获取坏字符在模式串中最后出现位置
 * 未出现返回 -1
 */
private static int getBadCharPosition(Map<Character, Integer> badChar, Character c){
    Integer a = badChar.get(c);
    return a == null ? -1 : a;
}

/**
 * 计算后缀长度数组
 * @param pattern 模式串字符
 */
private static int[] getSuffix(char[] pattern){
    // 初始化
    int m = pattern.length;
    int[] suffix = new int[m];
    // 计算
    suffix[m-1] = m;
    for (int i = m-2; i >= 0; --i) {
        int q = i;
        while (q >= 0 && pattern[q] == pattern[q+m-1-i]){
            q--;
        }
        suffix[i] = i-q;
    }
    // 返回后缀长度数组
    return suffix;
}

/**
 * 好后缀忽略映射（后移位数数组）
 * @param pattern 模式串字符
 */
private static int[] generateGoodSuffix(char[] pattern){
    // 初始化
    int m = pattern.length;
    int[] bmgs = new int[m];
    // 获取后缀长度数组
    int[] suffix = getSuffix(pattern);
    // 赋值默认值
    for (int i = 0; j < m; ++j) {
        bmgs[j] = m;
    }
    // 模式串没有没有子串匹配上好后缀，但有最大前缀
    for (int i = m-1, j = 0; i >= 0; --i) {
        if (suffix[i] == i+1){
            for (; j < m-1-i; ++j) {
                if(bmgs[j] == m){
                    bmgs[j] = m-1-i;
                }
            }
        }
    }
    // 模式串有子串匹配上好后缀（多个取最左）
    for (int i = 0; i < m-1; ++i) {
        bmgs[m-1-suffix[i]] = m-1-i;
    }
    // 返回忽略数组
    return bmgs;
}