ac算法 java

AC自动机是一种多模式串匹配算法，它可以在一个主串中查找多个模式串，其时间复杂度为O(n+m)，其中n为主串长度，m为模式串总长度。以下是AC自动机的Java实现：

import java.util.*;

// AC自动机节点类
class ACNode {
    public char val;
    public boolean isLeaf;
    public ACNode fail;
    public Map<Character, ACNode> children;

    public ACNode(char val) {
        this.val = val;
        this.isLeaf = false;
        this.fail = null;
        this.children = new HashMap<>();
    }
}

// AC自动机类
class AC {
    private ACNode root;

    public AC() {
        this.root = new ACNode('\0');
    }

    // 插入模式串
    public void insert(String s) {
        ACNode curr = this.root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!curr.children.containsKey(c)) {
                curr.children.put(c, new ACNode(c));
            }
            curr = curr.children.get(c);
        }
        curr.isLeaf = true;
    }

    // 构建fail指针
    public void buildFailPointer() {
        Queue<ACNode> queue = new LinkedList<>();
        for (ACNode child : this.root.children.values()) {
            queue.offer(child);
            child.fail = this.root;
        }
        while (!queue.isEmpty()) {
            ACNode curr = queue.poll();
            for (ACNode child : curr.children.values()) {
                queue.offer(child);
                ACNode fail = curr.fail;
                while (fail != null && !fail.children.containsKey(child.val)) {
                    fail = fail.fail;
                }
                child.fail = fail == null ? this.root : fail.children.get(child.val);
                child.isLeaf |= child.fail.isLeaf;
            }
        }
    }

    // 查找主串中的模式串
    public Set<String> search(String s) {
        Set<String> res = new HashSet<>();
        ACNode curr = this.root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            while (curr != this.root && !curr.children.containsKey(c)) {
                curr = curr.fail;
            }
            if (curr.children.containsKey(c)) {
                curr = curr.children.get(c);
            }
            if (curr.isLeaf) {
                res.add(getMatchedString(curr));
            }
        }
        return res;
    }

    // 获取匹配的模式串
    private String getMatchedString(ACNode node) {
        StringBuilder sb = new StringBuilder();
        while (node != this.root) {
            sb.append(node.val);
            node = node.fail;
        }
        return sb.reverse().toString();
    }
}

// 测试
public class Main {
    public static void main(String[] args) {
        AC ac = new AC();
        ac.insert("he");
        ac.insert("she");
        ac.insert("his");
        ac.insert("hers");
        ac.buildFailPointer();
        Set<String> res = ac.search("ushers");
        System.out.println(res); // [hers, she]
    }
}

上述代码中，ACNode类表示AC自动机的节点，其字段包括节点值val、是否为叶子节点isLeaf、fail指针fail、子节点映射表children。AC类表示AC自动机，其字段包括根节点root。AC类的方法包括insert()用于插入模式串、buildFailPointer()用于构建fail指针、search()用于查找主串中的模式串、getMatchedString()用于获取匹配的模式串。在测试代码中，我们插入了4个模式串，然后构建fail指针，最后在主串"ushers"中查找模式串，输出结果为[hers, she]。