AC 自动机

• OI Wiki: https://oi-wiki.org/string/ac-automaton/

题目	难度
3213. 最小代价构造字符串	困难

定义

AC（Aho–Corasick）自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的自动机，用于解决多模式匹配等任务。

AC 自动机本质上是 Trie 上的自动机。

3213. 最小代价构造字符串

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.function.Function;

public class Solution3213 {
    private static final int INF = (int) 1e9;

    public int minimumCost(String target, String[] words, int[] costs) {
        int n = target.length();
        int m = words.length;

        Node root = new Node(0);
        for (int i = 0; i < m; i++) {
            Node cur = root;
            for (char c : words[i].toCharArray()) {
                if (cur.next[c - 'a'] == null) {
                    cur.next[c - 'a'] = new Node(cur.len + 1);
                }
                cur = cur.next[c - 'a'];
            }
            cur.len = words[i].length();
            cur.cost = Math.min(cur.cost, costs[i]);
        }
        Queue<Node> q = new ArrayDeque<>();
        for (int i = 0; i < 26; i++) {
            if (root.next[i] == null) {
                root.next[i] = root;
            } else {
                root.next[i].fail = root;
                root.next[i].sup_fail = root;
                q.add(root.next[i]);
            }
        }
        for (; !q.isEmpty(); q.remove()) {
            Node u = q.peek();
            for (int i = 0; i < 26; i++) {
                if (u.next[i] == null) {
                    u.next[i] = u.fail.next[i];
                } else {
                    u.next[i].fail = u.fail.next[i];
                    if (u.next[i].fail.cost == INF) {
                        u.next[i].sup_fail = u.next[i].fail.sup_fail;
                    } else {
                        u.next[i].sup_fail = u.next[i].fail;
                    }
                    q.add(u.next[i]);
                }
            }
        }

        int[] dp = new int[n + 1];
        Node cur = root;
        for (int i = 0; i < n; i++) {
            cur = cur.next[target.charAt(i) - 'a'];
            int min_cost = INF;
            for (Node j = cur; j != null; j = j.sup_fail) {
                min_cost = Math.min(min_cost, dp[i + 1 - j.len] + j.cost);
            }
            dp[i + 1] = min_cost;
        }
        return dp[n] < INF ? dp[n] : -1;
    }

    static class Node {
        int len, cost;
        Node fail, sup_fail;
        Node[] next;

        public Node(int len) {
            this.len = len;
            cost = INF;
            next = new Node[26];
        }
    }
}

（全文完）