// 時(shí)間復(fù)雜度：O(n × m × k)
// 隨著敏感詞數(shù)量增加，性能急劇下降
for (String word : sensitiveWords) {
    if (text.contains(word)) {
        // 處理敏感詞
    }
}

public class TrieNode {
    // 子節(jié)點(diǎn)映射：字符 -> Trie節(jié)點(diǎn)
    private Map<Character, TrieNode> children = new HashMap<>();

    // 是否為敏感詞的結(jié)束節(jié)點(diǎn)
    private boolean isEnd = false;

    // 完整敏感詞內(nèi)容（便于輸出）
    private String keyword;

    public TrieNode getChild(char c) {
        return children.get(c);
    }

    public TrieNode addChild(char c) {
        return children.computeIfAbsent(c, k -> new TrieNode());
    }

    public boolean hasChild(char c) {
        return children.containsKey(c);
    }

    // getters and setters...
}

public class SensitiveWordFilter {
    private TrieNode root;
    private int minWordLength = 1;

    public SensitiveWordFilter(List<String> sensitiveWords) {
        this.root = buildTrie(sensitiveWords);
        this.minWordLength = sensitiveWords.stream()
            .mapToInt(String::length).min().orElse(1);
    }

    /**
     * 構(gòu)建 Trie 樹
     */
    private TrieNode buildTrie(List<String> words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.addChild(c);
            }
            node.setEnd(true);
            node.setKeyword(word);
        }
        return root;
    }

    /**
     * 檢查是否包含敏感詞 - 核心 DFA 匹配算法
     */
    public boolean containsSensitiveWord(String text) {
        if (text == null || text.length() < minWordLength) {
            return false;
        }

        char[] chars = text.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (dfaMatch(chars, i)) {
                return true;
            }
        }
        return false;
    }

    /**
     * DFA 狀態(tài)轉(zhuǎn)移匹配
     */
    private boolean dfaMatch(char[] chars, int start) {
        TrieNode node = root;

        for (int i = start; i < chars.length; i++) {
            char c = chars[i];

            if (!node.hasChild(c)) {
                break; // 狀態(tài)轉(zhuǎn)移失敗
            }

            node = node.getChild(c);

            if (node.isEnd()) {
                return true; // 到達(dá)接受狀態(tài)
            }
        }
        return false;
    }

    /**
     * 查找并替換敏感詞
     */
    public String filter(String text, String replacement) {
        List<SensitiveWordResult> words = findAllWords(text);

        // 從后往前替換，避免索引變化問題
        StringBuilder result = new StringBuilder(text);
        for (int i = words.size() - 1; i >= 0; i--) {
            SensitiveWordResult word = words.get(i);
            String stars = String.valueOf(replacement != null ? replacement : "*")
                .repeat(word.getEnd() - word.getStart() + 1);
            result.replace(word.getStart(), word.getEnd() + 1, stars);
        }
        return result.toString();
    }

    /**
     * 查找所有敏感詞
     */
    public List<SensitiveWordResult> findAllWords(String text) {
        List<SensitiveWordResult> results = new ArrayList<>();

        if (text == null || text.length() < minWordLength) {
            return results;
        }

        char[] chars = text.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            TrieNode node = root;
            int j = i;

            while (j < chars.length && node.hasChild(chars[j])) {
                node = node.getChild(chars[j]);
                j++;

                if (node.isEnd()) {
                    results.add(new SensitiveWordResult(
                        text.substring(i, j), i, j - 1));
                }
            }
        }
        return results;
    }
}

public class SensitiveWordResult {
    private String word;      // 敏感詞內(nèi)容
    private int start;        // 起始位置
    private int end;          // 結(jié)束位置

    public SensitiveWordResult(String word, int start, int end) {
        this.word = word;
        this.start = start;
        this.end = end;
    }

    // getters and toString...
}

public class ChatMessageFilter {
    private SensitiveWordFilter wordFilter;

    // 異步處理敏感詞檢測(cè)
    private ExecutorService filterExecutor = Executors.newFixedThreadPool(10);

    public CompletableFuture<Message> filterMessageAsync(Message message) {
        return CompletableFuture.supplyAsync(() -> {
            String content = message.getContent();

            if (wordFilter.containsSensitiveWord(content)) {
                // 實(shí)時(shí)替換
                String filtered = wordFilter.filter(content, "***");
                message.setContent(filtered);

                // 記錄敏感詞統(tǒng)計(jì)
                recordSensitiveWords(content);
            }

            return message;
        }, filterExecutor);
    }

    private void recordSensitiveWords(String content) {
        List<SensitiveWordResult> words = wordFilter.findAllWords(content);
        // 統(tǒng)計(jì)敏感詞出現(xiàn)頻率，用于優(yōu)化詞庫(kù)
        updateWordFrequency(words);
    }
}

public class ContentAuditor {
    private SensitiveWordFilter highRiskFilter;  // 高風(fēng)險(xiǎn)詞
    private SensitiveWordFilter mediumRiskFilter; // 中風(fēng)險(xiǎn)詞
    private SensitiveWordFilter lowRiskFilter;   // 低風(fēng)險(xiǎn)詞

    public AuditResult auditContent(String content) {
        AuditResult result = new AuditResult();

        // 按風(fēng)險(xiǎn)級(jí)別檢測(cè)
        List<SensitiveWordResult> highRiskWords = highRiskFilter.findAllWords(content);
        if (!highRiskWords.isEmpty()) {
            result.setStatus(AuditStatus.REJECT);
            result.setReason("包含高風(fēng)險(xiǎn)敏感詞");
            return result;
        }

        List<SensitiveWordResult> mediumRiskWords = mediumRiskFilter.findAllWords(content);
        if (!mediumRiskWords.isEmpty()) {
            result.setStatus(AuditStatus.MANUAL_REVIEW);
            result.setReason("包含中風(fēng)險(xiǎn)敏感詞，需要人工審核");
            return result;
        }

        List<SensitiveWordResult> lowRiskWords = lowRiskFilter.findAllWords(content);
        if (!lowRiskWords.isEmpty()) {
            // 低風(fēng)險(xiǎn)詞匯直接過濾
            String filtered = lowRiskFilter.filter(content, "***");
            result.setFilteredContent(filtered);
            result.setStatus(AuditStatus.PASS_WITH_FILTER);
        } else {
            result.setStatus(AuditStatus.PASS);
        }

        return result;
    }
}

@Service
public class SensitiveWordManager {
    private volatile SensitiveWordFilter filter;
    private ScheduledExecutorService updateExecutor =
        Executors.newSingleThreadScheduledExecutor();

    @PostConstruct
    public void init() {
        loadWords();
        // 定期更新詞庫(kù)
        updateExecutor.scheduleAtFixedRate(this::loadWords, 0, 1, TimeUnit.HOURS);
    }

    public void loadWords() {
        try {
            // 從數(shù)據(jù)庫(kù)或配置中心加載最新詞庫(kù)
            List<String> words = fetchLatestWords();
            SensitiveWordFilter newFilter = new SensitiveWordFilter(words);

            this.filter = newFilter;

            log.info("敏感詞庫(kù)更新完成，當(dāng)前詞數(shù)：{}", words.size());
        } catch (Exception e) {
            log.error("詞庫(kù)更新失敗", e);
        }
    }

    public boolean containsSensitiveWord(String text) {
        return filter != null && filter.containsSensitiveWord(text);
    }

    public String filterText(String text) {
        return filter != null ? filter.filter(text, "***") : text;
    }
}

// 雙數(shù)組結(jié)構(gòu)示意
int[] base = new int[size];  // 狀態(tài)轉(zhuǎn)移基礎(chǔ)值
int[] check = new int[size]; // 狀態(tài)轉(zhuǎn)移檢查值

// 狀態(tài)轉(zhuǎn)移：next_state = base[current_state] + char_code
// if check[next_state] == current_state: 轉(zhuǎn)移成功

public class AhoCorasickAutomaton {
    private Node root = new Node();

    // Trie 節(jié)點(diǎn)結(jié)構(gòu)
    static class Node {
        Map<Character, Node> children = new HashMap<>();
        Node fail;           // 失敗指針
        List<String> output = new ArrayList<>();  // 輸出模式
    }

    // 構(gòu)建自動(dòng)機(jī)
    public void build(List<String> patterns) {
        // 1. 構(gòu)建 Trie 樹
        for (String pattern : patterns) {
            Node node = root;
            for (char c : pattern.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new Node());
            }
            node.output.add(pattern);
        }

        // 2. 添加失敗指針
        Queue<Node> queue = new LinkedList<>();

        // 初始化根節(jié)點(diǎn)的子節(jié)點(diǎn)
        for (Node child : root.children.values()) {
            child.fail = root;
            queue.add(child);
        }

        // BFS 構(gòu)建失敗指針
        while (!queue.isEmpty()) {
            Node current = queue.poll();

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

                // 找到失敗指針
                Node failNode = current.fail;
                while (failNode != null && !failNode.children.containsKey(c)) {
                    failNode = failNode.fail;
                }

                child.fail = (failNode == null) ? root : failNode.children.get(c);
                child.output.addAll(child.fail.output);

                queue.add(child);
            }
        }
    }

    // 搜索匹配
    public List<MatchResult> search(String text) {
        List<MatchResult> results = new ArrayList<>();
        Node node = root;

        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);

            // 失敗指針跳轉(zhuǎn)
            while (node != null && !node.children.containsKey(c)) {
                node = node.fail;
            }

            node = (node == null) ? root : node.children.get(c);

            // 輸出匹配結(jié)果
            for (String pattern : node.output) {
                results.add(new MatchResult(pattern, i - pattern.length() + 1, i));
            }
        }

        return results;
    }

    // 匹配結(jié)果
    static class MatchResult {
        String pattern;
        int start;
        int end;

        public MatchResult(String pattern, int start, int end) {
            this.pattern = pattern;
            this.start = start;
            this.end = end;
        }
    }
}

// 分片處理示例
public class ShardedFilter {
	// 模擬分片
    private List<SensitiveWordFilter> shards;
    private BloomFilter<String> preFilter;

    public boolean containsSensitive(String text) {
        // 布隆過濾器預(yù)篩選
        if (!preFilter.mightContain(text)) {
            return false; // 肯定不包含敏感詞
        }

        // 分片精確匹配
        int shardIndex = text.hashCode() % shards.size();
        return shards.get(shardIndex).containsSensitiveWord(text);
    }
}