编辑代码

import java.util.*;
import java.util.function.*;


class SINGLE_MATCH {
	public static void main(String[] args) {
        List<AlgExtend> algList = new ArrayList<>();
        algList.add(AlgExtend.of(BF.class));
        algList.add(AlgExtend.of(RK.class));
        algList.add(AlgExtend.of(Sunday.class));
        algList.add(AlgExtend.of(KMP.class));
        algList.add(AlgExtend.of(BM.class));
        algList.add(AlgExtend.of(BM.class, () -> {BM.type = 0; return " BAD";}));
        algList.add(AlgExtend.of(BM.class, () -> {BM.type = 1; return " GOOD";}));

        // 
        algList.forEach(alg -> alg.run());
	}

    public static class AlgExtend {
        protected Class<?> algClass;
        protected Supplier<Object> before;
        protected Runnable after;

        public static AlgExtend of (Class<?> algClass) {
            return of(algClass, null);
        }

        public static AlgExtend of (Class<?> algClass, Supplier<Object> before) {
            return of(algClass, before, null);
        }

        public static AlgExtend of (Class<?> algClass, Supplier<Object> before, Runnable after) {
            assert algClass != null;
            
            AlgExtend alg = new AlgExtend();
            
            alg.algClass = algClass;
            alg.before = before;
            alg.after = after;
            
            return alg;
        }

        public void run () {
            Object key = null;
            if (before != null) key = before.get();
            // test("BF", (source, target) -> BF.bf(source, target));
            test(algClass.getSimpleName() + (key == null ? "" : key), (source, target) -> {
                try {
                    // 调用同名同参数的静态方法
                    return (Set<Word>) algClass.getMethod("check", String.class, String.class).invoke(null, source, target);
                } catch (Exception e) {
                    System.out.println(algClass.getSimpleName() + " 调用方法失败：" + e.getMessage());
                }
                return null;
            }); 
            if (after != null) after.run();
        }
    }

    public static void test (String algName, BiFunction<String, String, Set<Word>> task) {
        String target = "畜生";
        // 非临界
        Set<Word> words = task.apply("好好的人不做要做畜生，尽干些畜生的事", target);
        System.out.println(algName + "：" + words);
        // 尾部临界
        words = task.apply("畜生就是畜生", target);
        System.out.println(algName + "：" + words);
        // 尾部部分临界
        words = task.apply("畜生就不要妄想人的事，做一生的生畜", target);
        System.out.println(algName + "：" + words);
        // 重叠
        words = task.apply("GTGTGAGTGAGTGT", "GTGAGT");
        System.out.println(algName + "：" + words);
        words = task.apply("AGGAGAGAGAGA", "GAGAGA");
        System.out.println(algName + "：" + words);
    }

    public static class KMP {
        public static Set<Word> check (String source, String target) {
            assert !(isBlank(source) || isBlank(target)) && source.length() >= target.length(); // 非空并且source大于target
            int n = source.length(), m = target.length();
            // 构建next数组
            int[] next = buildKMPNext(target);
            
            Set<Word> result = new HashSet<>();

            int offset = 0, index = 0;
            for (; index < n; index++) {
                // 这里不同next构建过程，直接判断模式串的offset与主串index位置的字符
                while(offset > 0 && target.charAt(offset) != source.charAt(index)) {
                    offset = next[offset];// 回溯，裁剪模式串匹配位置
                }
                if (target.charAt(offset) == source.charAt(index)) {
                    offset++;// 移动模式串指针
                }
                if (offset == m) { // 模式串全部匹配了
                    result.add(Word.of(source.substring(index - m + 1, index + 1), index - m + 1));
                    offset = 0; // 重置
                }
            }

            return result;
        }

        private static int[] buildKMPNext (String pattern) {
            assert !isBlank(pattern);
            int[] next = new int[pattern.length()];
            // next[0] = next[1] = 0;
            int offset = 0, index = 2; // offset是“最长前缀的下一位置”，index是“已匹配前缀的下一位置”
            for (; index < next.length; index++) {
                while(offset > 0 && pattern.charAt(offset) != pattern.charAt(index - 1)) {
                    offset = next[offset]; // 回溯，减少“最长前缀”的字符
                }
                // 不论offset是否为0，都有可能相等
                if (pattern.charAt(offset) == pattern.charAt(index - 1)) {
                    offset++;// 当前位置加1
                }
                // offset有可能为0，也有可能非0
                next[index] = offset;
            }
            return next;
        }
    }

    public static class Sunday {
        public static Set<Word> check (String source, String target) {
            assert !(isBlank(source) || isBlank(target)) && source.length() >= target.length(); // 非空并且source大于target
            int n = source.length(), m = target.length();

            Set<Word> result = new HashSet<>();

            int start = 0, end = start + m - 1, offset;
            while (end < n) { // 遍历主串
                offset = 0;
                while (offset < m && source.charAt(start + offset) == target.charAt(offset)) ++offset; // 遍历模式串对应位置，相同一直匹配
                if (offset == m) {// 全部匹配了
                    result.add(Word.of(source.substring(start, start + m), start));
                    start = end + 1; // 整体跳过
                } else {// 不匹配
                    if(end == n - 1) {// 主串匹配到最后了，没必要往下处理
                        break;
                    }
                    // 查找end+1字符是否存在于模式串最右位置
                    offset = m - 1;
                    while (offset >= 0 && source.charAt(end + 1) != target.charAt(offset)) --offset;
                    if (offset >= 0) { // 存在
                        start += m - offset; // 移动到对应位置
                    } else {
                        start = end + 1; // 整体跳过
                    }
                }
                end = start + m - 1; // 更新
            }

            return result;
        }
    }

    public static class BM {
        public static int type = -1; // -1混合模糊、0坏字符、1好字符
        public static Set<Word> check (String source, String target) {
            return type == 0 ? bm_bad(source, target) : type == 1 ? bm_good(source, target) : bm_mix(source, target);
        }

        private static Set<Word> bm_mix (String source, String target) {
            assert !(isBlank(source) || isBlank(target)) && source.length() >= target.length(); // 非空并且source大于target
            int n = source.length(), m = target.length();
            
            int[] suffix = new int[m - 1];            // 最右原则：同一前缀子串在有多个匹配位置时，记录的是从左到右最晚出现/靠右的位置
            boolean[] prefix = new boolean[m - 1];    // 最左原则：匹配的前缀子串是否在模式串首位出现，即除了首位外，匹配的前缀子串就算出现在中间，也不影响该标记
            buildSuffixOfBMGood(target, suffix, prefix);

            Set<Word> result = new HashSet<>();

            int start = 0, offset;
            while (start <= n - m) {
                // System.out.println(source + " 查找：" + start);
                offset = m - 1;
                while (offset >= 0 && source.charAt(start + offset) == target.charAt(offset)) --offset;
                if (offset < 0) { // 模式串全都匹配了
                    result.add(Word.of(source.substring(start, start + m), start));
                    start += m; // 整体跳过
                    continue;
                }
                int badStep, goodStep = 0, badIndex = offset;
                offset = m - 1;
                // 坏字符
                while (offset >= 0 && target.charAt(badIndex) == target.charAt(offset)) --offset;
                badStep = badIndex - offset; // 有可能为负值：坏字符出现在badIndex之后的位置
                // System.out.println(source + " 查找坏字符：" + badStep);
                // 有好后缀
                if (badIndex < m - 1) {
                    goodStep = nextStepOfBMGood(badIndex, m, suffix, prefix);
                    // System.out.println(source + " 查找好后缀：" + goodStep);
                }
                // 取最大值
                start += Math.max(badStep, goodStep);
            }

            return result;
        }

        private static Set<Word> bm_bad (String source, String target) {
            assert !(isBlank(source) || isBlank(target)) && source.length() >= target.length(); // 非空并且source大于target
            int n = source.length(), m = target.length();
            
            Set<Word> result = new HashSet<>();

            int start = 0, offset;
            while (start >= 0 && start <= n - m) {
                // System.out.println("查询：" + start);
                offset = m - 1;
                while (offset >= 0 && source.charAt(start + offset) == target.charAt(offset)) --offset;
                if (offset < 0) { // 模式串全都匹配了
                    result.add(Word.of(source.substring(start, start + m), start));
                    start += m; // 整体跳过
                    continue;
                }
                int badIndex = offset;
                // 出现回退甚至越界现象
                // offset = m - 1;
                // 坏字符不存在就一直往前遍历
                // while (offset >= 0 && source.charAt(start + badIndex) != target.charAt(offset)) --offset;
                while (offset >= 0 && source.charAt(start + badIndex) != target.charAt(offset)) --offset;
                if (offset < 0) { // 都不存在
                    start += m;// 整体跳过
                    continue;
                }
                // 模式串存在坏字符
                start += badIndex - offset;
                // System.out.println("查询坏字符：" + start + " <<< " + offset + ", " + badIndex);
            }

            return result;
        }

        private static Set<Word> bm_good (String source, String target) {
            assert !(isBlank(source) || isBlank(target)) && source.length() >= target.length(); // 非空并且source大于target
            int n = source.length(), m = target.length();

            int[] suffix = new int[m - 1];            // 最右原则：同一前缀子串在有多个匹配位置时，记录的是从左到右最晚出现/靠右的位置
            boolean[] prefix = new boolean[m - 1];    // 最左原则：匹配的前缀子串是否在模式串首位出现，即除了首位外，匹配的前缀子串就算出现在中间，也不影响该标记
            buildSuffixOfBMGood(target, suffix, prefix);

            Set<Word> result = new HashSet<>();

            int start = 0, offset;
            while (start <= n - m) {
                offset = m - 1;
                while (offset >= 0 && source.charAt(start + offset) == target.charAt(offset)) --offset;
                if (offset == m - 1) { // 第一次匹配失败，即最后一个字符不相等，移动一位
                    start += 1;
                    continue;
                }
                if (offset < 0) { // 模式串全都匹配了
                    result.add(Word.of(source.substring(start, start + m), start));
                    start += m; // 整体跳过
                    continue;
                }
                // 不匹配，按规则对齐
                start += nextStepOfBMGood(offset, m, suffix, prefix);
            }

            return result;
        }

        /*
        * ========= 好后缀查找对齐偏移量 =========
        * badIndex 是不匹配字符在模式串的位置
        * m 是模式串的长度
        * suffix 作用的是 “好后缀”本身在模式串最右匹配的位置（非本身位置）；索引加1才表示后缀长度
        * prefix 作用的是 “好后缀”子后缀是否在模式串首位；索引加1才表示后缀长度
        */
        private static int nextStepOfBMGood (int badIndex, int m, int[] suffix, boolean[] prefix) {
            assert badIndex >= 0 && badIndex < m - 1; // badIndex不能是模式串最后一个字符位置
            // 好后缀 在模式串有匹配
            int lenIndex = m - (badIndex + 1) - 1; // 好后缀的长度-1才是对应索引
            if (suffix[lenIndex] != -1) {
                return (badIndex + 1) - suffix[lenIndex];
            }
            // 好后缀的子后缀 在模式串开头
            for (int i = badIndex + 2; i < m; i++) {
                if (prefix[m - i - 1]) { // m - i表示子后缀长度
                    return i;
                }
            }
            // 好后缀 及其 子后缀 都不符合，整体跳过
            return m;
        }

        /*
        * ========= 构建好后缀与最右匹配起始位置关系，以及其子后缀是否在模式串开头出现 =========
        * pattern是模式串内容
        * suffix 作用的是 “好后缀”本身在模式串最右匹配的位置（非本身位置）；索引加1才表示后缀长度
        * prefix 作用的是 “好后缀”子后缀是否在模式串首位；索引加1才表示后缀长度
        */
        private static void buildSuffixOfBMGood (String pattern, int[] suffix, boolean[] prefix) {
            assert !isBlank(pattern);
            int len = pattern.length();
            /*
                suffix 作用的是 “好后缀”本身在模式串最右匹配的位置（非本身位置）
                prefix 作用的是 “好后缀”子后缀是否在模式串首位
            */

            // 仅考虑模式串子串部分（即不含本身）；索引加1才表示后缀长度
            // int[] suffix = new int[len - 1];            // 最右原则：同一前缀子串在有多个匹配位置时，记录的是从左到右最晚出现/靠右的位置
            // boolean[] prefix = new boolean[len - 1];    // 最左原则：匹配的前缀子串是否在模式串首位出现，即除了首位外，匹配的前缀子串就算出现在中间，也不影响该标记
            for (int i = 0; i < len - 1; i++) {
                suffix[i] = -1;
            }

            for (int i = 0; i < len - 1; i++) { // 小于len - 1表示仅处理前缀子串，不含本身
                int offset = i          // 每个子串的结束位置
                    , lenIndex = 0;     // 每个子串的长度
                while (offset >= 0 && pattern.charAt(offset) == pattern.charAt(len - 1 - lenIndex)) { // 从后往前比较前缀子串的每个字符
                    suffix[lenIndex] = offset;  // 记录“好后缀”长度对应匹配前缀的起始位置
                    ++lenIndex;
                    --offset;
                }
                // 子串匹配到模式串的首位了
                if (offset == -1) {
                    prefix[lenIndex - 1] = true;
                }
            }

            // System.out.println(Arrays.toString(suffix));
            // System.out.println(Arrays.toString(prefix));
        }
    }

    public static class RK {
        // 匹配后，继续匹配下一个时，起始位置不会整体跳过，而是从下一字符开始
        public static Set<Word> check (String source, String target) {
            assert !(isBlank(source) || isBlank(target)) && source.length() >= target.length(); // 非空并且source大于target
            int n = source.length(), m = target.length();
            
            int i;
            int[] th = new int[]{0};
            hash(th, target, 0, m); // 模式串的hashcode
            // System.out.println(Arrays.toString(th));

            int[] sh = new int[n - m + 1];
            for (i = 0; i <= n - m; i++) {// 遍历主串生成各子串的hashcode
                hash(sh, source, i, m);
            }
            // System.out.println(Arrays.toString(sh));

            Set<Word> result = new HashSet<>();

            for (i = 0; i < sh.length; i++) {
                if (sh[i] == th[0]) {
                    result.add(Word.of(source.substring(i, i + m), i));
                }
            }
            
            return result;
        }

        /*
        * ========= 计算每个子串的hashcode =========
        * h是记录每个子串的数组
        * str是源串
        * si是子串相对于str的起始位置
        * len是子串长度
        */
        private static void hash (int[] h, String str, int si, int len) { // h数组代表的是每一个子串的hashcode，数组第二位起的hashcode无须遍历每个计算字符的hashcode，而是通过：数组上一位结果 - 数组上一位的首字符的hashcode + 当前计算的最后一位字符的hashcode
            assert !isBlank(str) && si >= 0 && len > 0 && si <= str.length() - len;
            if (si == 0) {
                h[0] = 0; // 初始化第一个
                for (int i = 0; i < len; i++) {
                    h[0] += calc(str.charAt(i), len - i - 1); // 迭代
                }
            } else {// 数组上一位结果 - 数组上一位的首字符的hashcode + 当前计算的最后一位字符的hashcode
                h[si] = h[si - 1] - calc(str.charAt(si-1), len - 1) + calc(str.charAt(si+len-1), 0);
            }
        }

        /*
        * ========= 计算单个字符的hashcode =========
        * c是待计算字符
        * exp是指数，采用进制数才会用到
        */
        private static int calc (Character c, int exp) {
            assert c != null && exp >= 0;
            return (c-'a'); // 加法
            // return (int)((c-'a') * Math.pow(26, exp)); // 26进制数
        }
    }

    public static class BF {
        // 匹配后，继续匹配下一个时，起始位置不会整体跳过，而是从下一字符开始
        public static Set<Word> check (String source, String target) {
            assert !(isBlank(source) || isBlank(target)) && source.length() >= target.length(); // 非空并且source大于target
            int n = source.length(), m = target.length();
            Set<Word> result = new HashSet<>();

            sl:for (int i = 0; i <= n - m; i++) { // 遍历主串
                for (int j = 0; j < m; j++) {// 遍历模式串
                    if(source.charAt(i+j) != target.charAt(j)) continue sl;
                }
                result.add(Word.of(target, i));
            }

            return result;
        }
    }

    public static boolean isBlank (String str) {
        return str == null || str.trim().isEmpty();
    }

    public static class Word {  // 保存匹配字符串及其源字符串的起始索引位置
        private int index;
        private String key;
        
        public static Word of (String key, int index) {
            assert key != null && index >= 0;
            
            Word word = new Word();
            
            word.index = index;
            word.key = key;
            
            return word;
        }

        public int getIndex () { return index; }
        public String getKey () { return key; }

        public String toString () {
            return "{\"key\":\"" + key + "\", \"index\":" + index + "}";
        }
    }
}