Java数据结构之AC自动机算法的实现

本文将详细讲解AC自动机算法在Java中的实现方法和原理，同时提供两个示例进行说明，使读者能够深入了解该算法并学会如何使用。

什么是AC自动机算法

AC自动机（Aho-Corasick Automaton）是多模式匹配的一种经典算法，其基本思路是将多个模式串构建成一颗“字典树”，然后对输入的文本串进行扫描匹配。相比于简单的暴力匹配方法，AC自动机算法可以在时间复杂度为O(n)的情况下实现多模式匹配，在诸如关键词过滤、字符串匹配等场景中具有很高的应用价值。

AC自动机算法的实现主要分为以下三个步骤：

1. 构建trie树：将所有模式串构建成一个trie树；
2. 对trie树进行预处理：为每个节点计算出其在trie树上的fail指针，并将所有模式串的状态存储到一个状态集合中；
3. 使用AC自动机模式匹配算法：对输入的文本串进行扫描匹配，每遇到一个字符就在trie树上进行前缀匹配，并跟随其相应的fail指针回溯到其下一个状态，直到匹配成功或达到文本串的末尾。

Java实现

构建trie树

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;
    Set<String> patterns;

    public TrieNode() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
        this.patterns = new HashSet<>();
    }
}

class Trie {
    private TrieNode root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        root = new TrieNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            curr.children.putIfAbsent(c, new TrieNode());
            curr = curr.children.get(c);
        }
        curr.isEndOfWord = true;
        curr.patterns.add(word); // 记录该节点所包含的所有模式串
    }
}

计算fail指针

class ACNode {
    char c; // 该节点代表的字符
    ACNode fail; // fail指针
    Map<Character, ACNode> children; // 子节点
    Set<String> patterns; // 存储该节点包含的所有模式串

    // 计算该节点的fail指针
    public void computeFailPointer() {
        Queue<ACNode> queue = new LinkedList<>();
        for (Map.Entry<Character, ACNode> entry : children.entrySet()) {
            char c = entry.getKey();
            ACNode child = entry.getValue();
            child.fail = this;
            queue.offer(child);
        }
        while (!queue.isEmpty()) {
            ACNode curr = queue.poll();
            for (Map.Entry<Character, ACNode> entry : curr.children.entrySet()) {
                char c = entry.getKey();
                ACNode child = entry.getValue();
                ACNode fail = curr.fail;
                while (fail != null && !fail.children.containsKey(c)) {
                    fail = fail.fail;
                }
                child.fail = fail == null ? this : fail.children.get(c);
                child.patterns.addAll(child.fail.patterns);
                queue.offer(child);
            }
        }
    }
}

class AC {
    private ACNode root;

    public AC(Trie trie) {
        root = new ACNode();
        for (Map.Entry<Character, TrieNode> entry : trie.root.children.entrySet()) {
            char c = entry.getKey();
            TrieNode child = entry.getValue();
            ACNode acChild = new ACNode();
            acChild.c = c;
            root.children.put(c, acChild);
            acChild.patterns.addAll(child.patterns);
            acChild.fail = root;
        }
        root.fail = root;
    }

    // 计算AC自动机的所有fail指针
    public void computeFailPointers() {
        root.computeFailPointer();
    }
}

AC自动机模式匹配

class ACAutomaton {
    private AC ac;

    public ACAutomaton(Trie trie) {
        ac = new AC(trie);
        ac.computeFailPointers();
    }

    public List<String> findAllOccurrences(String text) {
        List<String> res = new ArrayList<>();
        ACNode curr = ac.root;
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            while (curr != null && !curr.children.containsKey(c)) {
                curr = curr.fail;
            }
            if (curr == null) {
                curr = ac.root;
            } else {
                curr = curr.children.get(c);
                curr.patterns.forEach(res::add);
            }
        }
        return res;
    }
}

示例说明

示例一

假设有字符串集合{“she”, “he”, “say”, “sh”, “shr”, “her”}，并且要在下面这段文本中找出所有的模式串：

she says he has her shrubs

对该文本进行扫描匹配，最终找出的模式串是：

she, he, her, shr, say

示例二

假设有字符串集合{“cc”, “ccc”, “cccc”}，并且要在下面这段文本中找出所有的模式串：

abccccde

对该文本进行扫描匹配，最终找出的模式串是：

cc, ccc, cccc

总结

以上是AC自动机算法在Java中的实现方法和原理，本文详细讲解了AC自动机的实现过程和三个步骤，并同时提供了两个示例，希望能够帮助读者深入了解该算法并学会使用。