Java实现AC自动机进行高效多模式匹配

AC自动机是一种能够高效地在一个文本中同时搜索多个模式字符串的数据结构。其核心在于结合了Trie树和KMP算法的优点，能够在O(n)的时间复杂度内完成搜索，其中n是文本的长度。

在实现AC自动机的过程中，首先需要理解两个基本概念：

• Trie树（前缀树）：一种树形数据结构，用于存储一组字符串，每个节点代表一个字符，从根节点到任意节点的路径表示一个字符串。


• KMP算法：一种改进的字符串匹配算法，通过预处理模式字符串来避免不必要的比较，提高匹配效率。

以下是使用Java实现AC自动机的一个示例代码：

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;

public class AhoCorasickSearch {

    private static class TrieNode {
        private TrieNode parent;
        private TrieNode failure;
        private char value;
        private ArrayList results;
        private Hashtable children;

        public TrieNode(TrieNode parent, char value) {
            this.parent = parent;
            this.value = value;
            this.results = new ArrayList<>();
            this.children = new Hashtable<>();
        }

        public void addChild(TrieNode child) {
            children.put(child.value, child);
        }

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

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

        public void addResult(String pattern) {
            if (!results.contains(pattern)) {
                results.add(pattern);
            }
        }

        public ArrayList getResults() {
            return results;
        }

        public TrieNode getFailure() {
            return failure;
        }

        public void setFailure(TrieNode failure) {
            this.failure = failure;
        }

        public TrieNode getParent() {
            return parent;
        }
    }

    private TrieNode root;

    public AhoCorasickSearch(String[] patterns) {
        buildTrie(patterns);
        setFailures();
    }

    private void buildTrie(String[] patterns) {
        root = new TrieNode(null, '\0');
        for (String pattern : patterns) {
            TrieNode current = root;
            for (char c : pattern.toCharArray()) {
                if (!current.containsChild(c)) {
                    current.addChild(new TrieNode(current, c));
                }
                current = current.getChild(c);
            }
            current.addResult(pattern);
        }
    }

    private void setFailures() {
        Queue queue = new LinkedList<>();
        for (TrieNode child : root.getChildren()) {
            child.setFailure(root);
            queue.offer(child);
        }

        while (!queue.isEmpty()) {
            TrieNode current = queue.poll();
            for (TrieNode child : current.getChildren()) {
                TrieNode failure = current.getFailure();
                while (failure != null && !failure.containsChild(child.value)) {
                    failure = failure.getFailure();
                }
                child.setFailure(failure != null ? failure.getChild(child.value) : root);
                queue.offer(child);
            }
        }
    }

    public ArrayList findPatterns(String text) {
        ArrayList results = new ArrayList<>();
        TrieNode current = root;
        for (int i = 0; i             char c = text.charAt(i);
            while (current != root && !current.containsChild(c)) {
                current = current.getFailure();
            }
            current = current.containsChild(c) ? current.getChild(c) : root;
            for (String pattern : current.getResults()) {
                results.add(new StringSearchResult(i - pattern.length() + 1, pattern));
            }
        }
        return results;
    }
}

上述代码首先定义了一个内部类TrieNode，用于表示Trie树中的每个节点。接着，AhoCorasickSearch类实现了AC自动机的主要功能，包括构建Trie树、设置失败指针以及搜索模式字符串。

通过这种方法，我们可以高效地在一个文本中查找多个模式字符串，而无需对每个模式单独进行搜索，极大地提高了搜索效率。