public List<String> bruteForceMatch(String text, List<String> words) {
    List<String> result = new ArrayList<>();
    for (String word : words) {              // O(n)：遍历每个敏感词
        if (text.contains(word)) {           // O(L × m)：朴素子串匹配
            result.add(word);
        }
    }
    return result;
}

public class SimpleTrie {
    private static class Node {
        Map<Character, Node> children = new HashMap<>();
        boolean isEnd;
    }

    private final Node root = new Node();

    // 添加敏感词
    public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new Node());
        }
        node.isEnd = true;
    }

    // 检测文本中是否包含敏感词
    public boolean contains(String text) {
        for (int i = 0; i < text.length(); i++) {
            Node node = root;
            for (int j = i; j < text.length(); j++) {
                node = node.children.get(text.charAt(j));
                if (node == null) break;
                if (node.isEnd) return true;
            }
        }
        return false;
    }

    // 获取文本中所有匹配的敏感词
    public List<String> matchAll(String text) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < text.length(); i++) {
            Node node = root;
            for (int j = i; j < text.length(); j++) {
                node = node.children.get(text.charAt(j));
                if (node == null) break;
                if (node.isEnd) {
                    result.add(text.substring(i, j + 1));
                }
            }
        }
        return result;
    }
}

public class AhoCorasickAutomaton {
    private static class Node {
        Map<Character, Node> children = new HashMap<>();
        Node fail;                    // 失配指针
        List<String> outputs = new ArrayList<>(); // 该状态对应的匹配词
    }

    private final Node root = new Node();

    // 第一步：构建 Trie 树
    public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new Node());
        }
        node.outputs.add(word); // 末尾节点记录匹配词
    }

    // 第二步：构建 fail 指针（BFS）
    public void buildFailPointer() {
        Queue<Node> queue = new LinkedList<>();
        root.fail = root;

        // 根节点的直接子节点，fail 指向根
        for (Node child : root.children.values()) {
            child.fail = root;
            queue.offer(child);
        }

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            for (Map.Entry<Character, Node> entry : current.children.entrySet()) {
                char c = entry.getKey();
                Node child = entry.getValue();

                // 沿父节点的 fail 链查找是否有字符 c 的转移
                Node fail = current.fail;
                while (fail != root && !fail.children.containsKey(c)) {
                    fail = fail.fail;
                }
                child.fail = fail.children.getOrDefault(c, root);
                // 避免自环：如果 fail 指向了自己，改为指向根
                if (child.fail == child) {
                    child.fail = root;
                }
                // 合并 fail 节点的输出（关键！）
                child.outputs.addAll(child.fail.outputs);
                queue.offer(child);
            }
        }
    }

    // 第三步：模式匹配（单次扫描）
    public List<String> match(String text) {
        List<String> result = new ArrayList<>();
        Node state = root;

        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            // 沿 fail 链找到能处理字符 c 的状态
            while (state != root && !state.children.containsKey(c)) {
                state = state.fail;
            }
            state = state.children.getOrDefault(c, root);
            // 收集当前状态的所有匹配词（已通过 fail 链合并）
            result.addAll(state.outputs);
        }
        return result;
    }
}

AhoCorasickAutomaton ac = new AhoCorasickAutomaton();
ac.addWord("she");
ac.addWord("he");
ac.addWord("her");
ac.addWord("hers");
ac.buildFailPointer(); // 插入完所有词后，构建一次 fail 指针

List<String> matches = ac.match("ushers");
// 输出: [she, he, her, hers]

WordTree wordTree = new WordTree();
wordTree.addWord("大");
wordTree.addWord("大憨憨");
wordTree.addWord("憨憨");

String text = "那人真是个大憨憨！";

// 获得第一个匹配的关键字
String matchStr = wordTree.match(text);
System.out.println(matchStr); // 输出: 大

// matchAll(text, limit, isDensityMatch, isGreedy)
// - limit: 匹配数量上限，-1 表示不限制
// - isDensityMatch: 是否密度匹配（在已匹配词内部继续寻找重叠词）
// - isGreedy: 是否贪婪匹配（true 匹配最长关键词，false 匹配最短关键词）
List<String> matchStrList = wordTree.matchAll(text, -1, false, false);
System.out.println(matchStrList); // 输出: [大, 憨憨]

List<String> matchStrList2 = wordTree.matchAll(text, -1, false, true);
System.out.println(matchStrList2); // 输出: [大, 大憨憨]

public String preprocess(String text) {
    StringBuilder sb = new StringBuilder();
    for (char c : text.toCharArray()) {
        c = toHalfWidth(c);                    // 全角转半角
        c = Character.toLowerCase(c);          // 统一小写
        if (isChineseOrAlphanumeric(c)) {      // 保留中文和字母数字
            sb.append(c);
        }
    }
    return toSimplifiedChinese(sb.toString()); // 繁转简
}

private char toHalfWidth(char c) {
    if (c >= 'Ａ' && c <= 'Ｚ') return (char) (c - 'Ａ' + 'A');
    if (c >= 'ａ' && c <= 'ｚ') return (char) (c - 'ａ' + 'a');
    if (c >= '０' && c <= '９') return (char) (c - '０' + '0');
    return c;
}

private boolean isChineseOrAlphanumeric(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
        || (c >= '0' && c <= '9') || (c >= '\u4e00' && c <= '\u9fa5');
}

public class SensitiveWordFilter {
    private final AtomicReference<SimpleTrie> trieRef;

    public SensitiveWordFilter(List<String> initialWords) {
        this.trieRef = new AtomicReference<>(buildTrie(initialWords));
    }

    // 匹配时获取当前 Trie
    public List<String> match(String text) {
        SimpleTrie trie = trieRef.get();
        return trie != null ? trie.matchAll(text) : Collections.emptyList();
    }

    // 更新词库：先构建新 Trie，再原子发布
    public void refreshWords(List<String> newWords) {
        SimpleTrie newTrie = buildTrie(newWords);
        trieRef.set(newTrie);  // 原子发布，对读线程立即可见
    }

    private SimpleTrie buildTrie(List<String> words) {
        SimpleTrie trie = new SimpleTrie();
        for (String word : words) {
            trie.addWord(word);
        }
        return trie;
    }
}

// 使用独立线程池，避免占用 ForkJoinPool.commonPool()
private final ExecutorService filterExecutor =
    new ThreadPoolExecutor(
        4, 8, 60L, TimeUnit.SECONDS,
        LinkedBlockingQueue<>(1000),
        new ThreadPoolExecutor.CallerRunsPolicy() // 队列满时由调用线程执行，实现背压
    );

public List<String> parallelMatch(String text, int chunkSize, int maxWordLength) {
    // 重叠区域 = 最长敏感词长度 - 1，防止跨边界漏词
    int overlap = maxWordLength - 1;
    List<CompletableFuture<List<String>>> futures = new ArrayList<>();

    for (int i = 0; i < text.length(); i += chunkSize) {
        int start = i;
        int end = Math.min(i + chunkSize + overlap, text.length());
        String chunk = text.substring(start, end);

        // 显式传入自定义线程池
        futures.add(CompletableFuture.supplyAsync(() ->
            trieRef.get().matchAll(chunk), filterExecutor
        ));
    }

    return futures.stream()
        .flatMap(f -> f.join().stream())
        .distinct()
        .collect(Collectors.toList());
}

public List<String> matchWithBloomFilter(String text, int maxWordLength) {
    // 快速检测：扫描所有可能的子串
    if (!quickCheck(text, maxWordLength)) {
        return Collections.emptyList();  // 确定不包含敏感词
    }
    // 可能包含敏感词，进行精确匹配
    return trieRef.get().matchAll(text);
}

private boolean quickCheck(String text, int maxWordLen) {
    BloomFilter<String> filter = getBloomFilter();  // 包含所有敏感词的布隆过滤器
    for (int i = 0; i < text.length(); i++) {
        for (int len = 1; len <= maxWordLen && i + len <= text.length(); len++) {
            if (filter.mightContain(text.substring(i, i + len))) {
                return true;  // 可能包含，需精确匹配
            }
        }
    }
    return false;  // 确定不包含
}