Java 求调
查看原帖
Java 求调
797349
yelanyanyu楼主2022/12/20 10:53

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class ACAutomation {
    private static InputReader in = new InputReader();
    private static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = in.nextInt();
        AC ac = new AC();
        for (int i = 0; i < n; i++) {
            ac.insert(in.next());
        }
        List<String> list = ac.containWords(in.next());
        out.println(list.size());
        in.bf.close();
        out.close();
    }

    private static class MyQueue {
        private int last;
        private int first;
        private Node[] arr;

        public MyQueue(int size) {
            arr = new Node[size];
            last = 0;
            first = 0;
        }

        public void add(Node node) {
            if (node != null && last < arr.length) {
                arr[last++] = node;
            }
        }

        public Node poll() {
            if (!isEmpty()) {
                return arr[first++];
            }
            return null;
        }

        public boolean isEmpty() {
            return first == last;
        }
    }


    private static class Node {
        public String end;
        public int ends;
        public boolean endUse;
        public Node fail;
        public Node[] nexts;

        public Node() {
            endUse = false;
            end = null;
            ends = 0;
            fail = null;
            nexts = new Node[26];
        }
    }

    /**
     * AC自动机
     */
    public static class AC {
        private Node root;

        public AC() {
            root = new Node();
        }

        /**
         * 插入节点但不构建fail指针
         *
         * @param str
         */
        public void insert(String str) {
            char[] strs = str.toCharArray();
            int index = -1;
            Node cur = root;
            for (int i = 0; i < strs.length; i++) {
                index = strs[i] - 'a';
                if (cur.nexts[index] == null) {
                    cur.nexts[index] = new Node();
                }
                cur = cur.nexts[index];
            }
            cur.end = str;
            cur.ends++;
        }

        /**
         * BFS构建fail指针
         */
        public void buildFail() {
            MyQueue queue = new MyQueue(1000000);
            Node cur = root;
            Node curFail = null;
            queue.add(root);
            //BFS
            while (!queue.isEmpty()) {
                cur = queue.poll();
                for (int i = 0; i < root.nexts.length; i++) {
                    if (cur.nexts[i] != null) {
                        cur.nexts[i].fail = root;
                        curFail = cur.fail;
                        while (curFail != null) {
                            if (curFail.nexts[i] != null) {
                                cur.nexts[i].fail = curFail.nexts[i];
                                break;
                            }
                            curFail = curFail.fail;
                        }
                        queue.add(cur.nexts[i]);
                    }
                }
            }
        }

        public List<String> containWords(String content) {
            char[] str = content.toCharArray();
            int index = 0;
            Node follow = root;
            Node cur = root;
            ArrayList<String> list = new ArrayList<>();
            //构建fail指针
            buildFail();
            for (int i = 0; i < str.length; i++) {
                index = str[i] - 'a';
                //若没有可以走的路径,就沿着fail指针走
                while (cur.nexts[index] == null && cur != root) {
                    cur = cur.fail;
                }
                //cur更新到下一个节点
                cur = cur.nexts[index] == null ? root : cur.nexts[index];
                //follow遍历fail指针,将匹配到的加入list中
                follow = cur;
                while (follow != root) {
                    //当前位置已经加入过list中了
                    if (follow.endUse) {
                        break;
                    }
                    //当前位置是模式串的结尾,加入list
                    if (follow.end != null) {
                        for (int j = 0; j < cur.ends; j++) {
                            list.add(follow.end);
                        }
                        //表示已经匹配过了
                        follow.endUse = true;
                    }
                    follow = follow.fail;
                }
            }
            return list;
        }
    }

    /**
     * 输入输出优化
     */
    public static class InputReader {
        private StringTokenizer st;
        private BufferedReader bf;

        public InputReader() {
            bf = new BufferedReader(new InputStreamReader(System.in));
            st = null;
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return bf.readLine();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() throws IOException {
            return new BigInteger(next());
        }

        public BigDecimal nextBigDecimal() throws IOException {
            return new BigDecimal(next());
        }
    }
}

2022/12/20 10:53
加载中...