AC自动机java模板题u301874

以下是AC自动机Java模板题U301874的代码实现：

import java.io.*;
import java.util.*;

public class Main {
    static final int MAXN = 100010, MAXM = 200010;
    static final int INF = 0x3f3f3f3f;

    static int n, m, cnt;
    static int[] trie = new int[MAXN * 30], idx = new int[MAXN * 30];
    static int[] fail = new int[MAXN * 30], vis = new int[MAXN * 30];
    static int[] head = new int[MAXN], nxt = new int[MAXM], ver = new int[MAXM], tot;
    static int[] deg = new int[MAXN];
    static char[][] str = new char[MAXN][30];
    static Map<Character, Integer> map = new HashMap<>();

    static int add(char[] s) {
        int p = 0;
        for (int i = 0; s[i] != '\0'; i++) {
            char c = s[i];
            if (!map.containsKey(c)) {
                map.put(c, ++cnt);
            }
            int u = map.get(c);
            if (trie[p] == 0) {
                trie[p] = ++tot;
            }
            p = trie[p];
            idx[p] = u;
        }
        return p;
    }

    static void build() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= cnt; i++) {
            int u = map.get(str[i][0]);
            if (trie[0] == 0) {
                trie[0] = ++tot;
            }
            int p = trie[0];
            idx[p] = 0;
            if (trie[p + u] == 0) {
                trie[p + u] = ++tot;
            }
            fail[p + u] = p;
            q.offer(p + u);
        }
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int i = head[idx[u]]; i != 0; i = nxt[i]) {
                int v = ver[i];
                int p = fail[u], q = 0;
                while (p != 0 && trie[p + v] == 0) {
                    p = fail[p];
                }
                if (trie[p + v] != 0) {
                    q = trie[p + v];
                }
                fail[u + v] = q;
                q.offer(u + v);
            }
        }
    }

    static void addEdge(int u, int v) {
        ver[++tot] = v;
        nxt[tot] = head[u];
        head[u] = tot;
    }

    static void topo() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= tot; i++) {
            if (deg[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int u = q.poll();
            vis[u] = 1;
            for (int i = head[u]; i != 0; i = nxt[i]) {
                int v = ver[i];
                deg[v]--;
                if (deg[v] == 0) {
                    q.offer(v);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            String s = in.next();
            str[i] = s.toCharArray();
            add(str[i]);
        }
        m = in.nextInt();
        for (int i = 1; i <= m; i++) {
            String s = in.next();
            int len = s.length();
            int p = 0;
            for (int j = 0; j < len; j++) {
                char c = s.charAt(j);
                if (!map.containsKey(c)) {
                    break;
                }
                int u = map.get(c);
                if (trie[p + u] == 0) {
                    break;
                }
                p = trie[p + u];
                deg[p]++;
                addEdge(p, p + u);
            }
        }
        build();
        topo();
        for (int i = 1; i <= n; i++) {
            int p = 0;
            for (int j = 0; str[i][j] != '\0'; j++) {
                p = trie[p + map.get(str[i][j])];
                if (vis[p] == 1) {
                    System.out.println("YES");
                    break;
                }
            }
            if (vis[p] == 0) {
                System.out.println("NO");
            }
        }
    }
}

该题解释：给定 $n$ 个模式串和 $m$ 个文本串，问每个模式串是否存在于文本串中。其中，模式串和文本串都只包含小写字母。

AC自动机是一种可以高效匹配多个模式串的数据结构。该题需要使用AC自动机进行多模式串匹配。

代码实现中，使用一个trie树存储所有模式串，每个节点记录了下一层的字符和对应的子节点编号。同时，使用一个map记录每个字符对应的编号，以便于在trie树中查找。

在trie树构建完成后，使用广度优先搜索构建fail指针。搜索过程中，对于每个节点 $u$，依次查找其父亲节点 $p$ 直到根节点，若 $p$ 的子节点 $v$ 与 $u$ 的子节点 $w$ 匹配，则令 $u$ 的fail指针指向 $p+v$ 节点。如果 $p+v$ 节点不存在，则继续向根节点搜索。

在fail指针构建完成后，对于每个文本串，从根节点开始依次匹配每个字符，直到匹配完成或者无法匹配。如果最终匹配的节点已经被访问，则说明该模式串存在于文本串中。

时间复杂度为 $O(\sum |P|+|T|)$，其中 $\sum |P|$ 表示所有模式串的长度之和，$|T|$ 表示所有文本串的长度之和。