编辑代码

import java.util.*;
import java.util.stream.*;
import java.util.concurrent.*;


class Main {
	public static void main(String[] args) {
        //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。
        FED fed = new FED ();
        fed.add("傻逼", "FK", "脑残");
		System.out.println(fed.getDict());
        
		System.out.println(fed.check("我不和傻逼玩，万一也脑残就不好了~"));
	}

    public static class FED {
        // 移除操作时，maxLength、first和end比较不好处理（除非引入其他计数器关联），直接不处理
        private boolean[] first = new boolean[Character.MAX_VALUE]; // 索引值可能超出char，为负值，但影响不大
        private boolean[] end = new boolean[Character.MAX_VALUE];
        private int maxLength;

        // 词库字典
        private final Map<Integer, Set<String>> wordDict = new ConcurrentHashMap<>(1024);

        public Set<Word> check (String text) {
            Set<Word> result = new HashSet<>();

            if (isNotBlank(text)) {
                int len = text.length();
                int[] start = new int[maxLength];
                int firstCount = 0,     // 记录 模式串的首字符 的个数
                    oldestOffset = 0;   // 记录 在maxLength范围内，最旧的模式串的首字符 的偏移，用来控制循环的起始边界
                for (int i = 0; i < len; i++) {
                    char c = text.charAt(i);
                    // 是模式串的首字符
                    if (first[c]) {
                        // 在maxLength范围内，最旧的模式串的首字符 循环偏移；firstCount < maxLength不需要移动
                        oldestOffset = firstCount < maxLength ? 0 : (1 + (firstCount % maxLength)) % maxLength;
                        start[firstCount++ % maxLength] = i;
                    }
                    // 匹配过模式串的首字符，也是模式串的尾字符
                    if (firstCount > 0 && end[c]) {
                        // offsetFirst指向头字符位置，模式串不存在时，从右向左移动找下一个头字符（另一个模式串）位置
                        int hash = 0, offsetFirst = firstCount - 1;
                        // 从尾字符往前遍历，直到最旧匹配的头字符的位置：本质就是遍历次数是小于MAX_WORD_LENGTH的某个值
                        for (int j = i + 1; --j >= start[oldestOffset]; ) {
                            hash = hash (hash, text.charAt(j));
                            // 到首字符位置了
                            if (j == start[offsetFirst % maxLength]) {
                                --offsetFirst;
                                if (wordDict.containsKey(hash)) {
                                    String word = text.substring(j, i + 1);
                                    if (wordDict.get(hash).contains(word)) {
                                        result.add(Word.of(word, j));
                                        // 是否考虑重置呢
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
            }

            return result;
        }

        public void add (String... words) {
            if (words != null && words.length > 0) {
                Arrays.asList(words).stream().filter(Objects::nonNull).collect(Collectors.toSet()).stream().forEach(this::add);
            }
        }

        public Map<Integer, Set<String>> getDict () {
            return this.wordDict;
        }

        private void add (String pattern) {
            assert isNotBlank(pattern);
            int len = pattern.length();
            // 构建首尾数组
            first[pattern.charAt(0)] = true;
            end[pattern.charAt(len - 1)] = true;
            if (len > maxLength) {
                maxLength = len;
            }
            // 构建词库字典
            int hash = 0;
            for (int i = len; --i >= 0;) { // 逆向高位计算，为了查找是方便
                hash = hash(hash, pattern.charAt(i));
            }
            // 将模式串保存到字典中，不存在则创建后在保存
            wordDict.computeIfAbsent(hash, k -> new HashSet<>()).add(pattern);
        }

        /*
        * ============= 计算字符hashcode =============
        * hash是高位值
        * c是低位值
        */
        private int hash (int hash, Character c) {
            return 31 * hash + c;
        }

        private boolean isNotBlank (String str) {
            return str != null && str.trim().length() > 0;
        }
    }

    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 + "}";
        }
    }
}